Сипаттама
$1$-ден $n$-ге дейін нөмірленген $n$ төбесі бар бағытталған граф берілген. Әрбір $1 \le i \le n$ төбесі үшін $i$ төбесінің шығыс дәрежесі бірден аспайды; сондықтан біз графты $p_i$ массиві арқылы сипаттай аламыз, мұнда егер $i$ төбесінің шығыс дәрежесі нөлге тең болса, $p_i = 0$, ал кері жағдайда $1 \le p_i \le n$, $p_i \ne i$ және $i$-ден $p_i$-ге бағытталған қыр бар. Графта бағытталған циклдер жоқ, сондықтан кез келген $i$ төбесінен бастап бағытталған қырлар бойымен келесі төбеге қайта-қайта өту арқылы құрылған жол түбінде шығыс дәрежесі нөлге тең төбеде аяқталады.
Бастапқыда төбелердің бірінде ағаш дойбы тасы тұр. Сіз алақан соққанда, егер тас $p_i$ мәні нөлден өзгеше $i$ төбесінде тұрса, ол $p_i$ төбесіне жылжиды; әйтпесе орнынан қозғалмайды. Алайда сіз тастың қайда екенін мүлдем көре алмайсыз — сіз жасай алатын жалғыз амал: төбелердің ішкі жиынын таңдап, тасты таңдалған төбелердің біріне қойып, бірнеше рет алақан соғып, тастың сіз таңдаған төбелердің бірінде тоқтағанын не тоқтамағанын бақылау. Тіпті тастың бастапқы орны мен алақан соғу санын да интерактор таңдайды: сіз тек төбелердің ішкі жиынын таңдай аласыз және тас сіз таңдаған төбелердің бірінен бастап, сіз таңдаған төбелердің бірінде аяқтай алатындай етіп ең көп дегенде неше рет алақан соғуға болатынын бақылай аласыз.
Сіз бүкіл графта бұрынғыдан да көپ рет алақан соға алу үшін $x$-тен $y$-ке ($1 \le x, y \le n$, $x \ne y$ және $p_x = 0$, яғни $p_x = y$ деп қоюға болады) бір қыр қосқыңыз келеді. Дегенмен, бұл қырды қосу графта ешқандай бағытталған цикл тудырмауы тиіс.
Төбелердің ең көбі $n$ ішкі жиынында алақан соғудың максималды санын сұрау арқылы қосуға болатын осындай кез келген қырды табыңыз немесе мұндай қырды қосу мүмкін емес екенін анықтаңыз.
Кіріс деректер
Кіріс деректердің бірінші жолында бір бүтін сан $n$ ($1 \le n \le 1000$) берілген.
Өзара әрекеттесу
Сұраныс жасау үшін $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$ түріндегі бір жолды шығарыңыз, мұндағы $1 \le k \le n$, ал $1 \le u_i \le n$ — сіз таңдаған ішкі жиындағы қос-қостан әртүрлі төбелер. Содан кейін бір бүтін саннан тұратын бір жолды оқыңыз: тас сіз таңдаған төбелердің бірінен басталып, таңдаған төбелердің бірінде аяқтала алатындай етіп алақан соғудың максималды саны. Сіз ең көбі $n$ сұраныс жасай аласыз.
Қосқыңыз келетін қырды анықтағаннан кейін, $\texttt{! } x \text{ } y$ түріндегі бір жолды шығарыңыз, мұндағы $1 \le x, y \le n$ — сіз қосқыңыз келетін бағытталған қырдың ұштары. Егер шешімдер бірнешеу болса, кез келгенін шығаруға болады.
Егер мұндай қырды қосу мүмкін болмаса, қырдың ұштарының орнына $-1 \text{ -1}$ шығарыңыз.
Жауапты шығарғаннан кейін бағдарламаңыз бірден жұмысын аяқтауы тиіс.
Әрбір сұраныстан кейін шығыс буферін тазалаңыз (flush).
Интерактор бейімделгіш емес; граф алдын ала бекітілген.
Мысал
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Ескертпе
