Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 1024 MB 總分: 100 互動
统计

Сипаттама

$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

Ескертпе

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.