Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Interactive
Statistics

Опис

Дано орієнтований граф на $n$ вершинах, пронумерованих від $1$ до $n$. Для кожної вершини $1 \le i \le n$ напівстепінь виходу вершини $i$ не перевищує одиниці; отже, ми можемо описати граф за допомогою масиву $p_i$, де $p_i = 0$, якщо напівстепінь виходу вершини $i$ дорівнює нулю, а інакше $1 \le p_i \le n$, $p_i \ne i$, і існує орієнтоване ребро з $i$ до $p_i$. У графі немає орієнтованих циклів, тому з будь-якої вершини $i$ шлях, утворений послідовним переходом до наступної вершини вздовж орієнтованих ребер, зрештою закінчиться у вершині з нульовим напівстепенем виходу.

Спочатку на одній із вершин стоїть дерев'яна шашка. Коли ви плескаєте в долоні, якщо шашка перебуває у вершині $i$ з ненульовим $p_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.