Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

E. Мой разум гибнет
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

От скуки вы решили скоротать время, сыграв с бортовым суперкомпьютером в придуманную вами игру. Игра проходит следующим образом: суперкомпьютер показывает вам двудольный граф $$$G$$$ на $$$n$$$ вершинах, после чего выбирает секретную пару различных ребер $$$e_1$$$ и $$$e_2$$$, отсутствующих в нем, обладающих следующими свойствами:

  • граф $$$G \cup \{e_1\}$$$ двудольный;
  • граф $$$G \cup \{e_2\}$$$ двудольный;
  • граф $$$G' = G \cup \{e_1, e_2\}$$$ не двудольный.

Ваша задача — найти хотя бы одно из загаданных ребер. Для этого вы можете использовать два типа запросов:

  • ? 1 $$$k \; v_1 \; v_2 \; \ldots \; v_k$$$ ($$$1 \le k \le n$$$, все $$$v_i$$$ различны): выбрать множество из $$$k$$$ вершин и узнать, является ли двудольным подграф $$$G'$$$, состоящий только из этих вершин и ребер $$$G'$$$, их соединяющих;
  • ? 2 $$$u \; v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$): узнать, содержит ли $$$G'$$$ ребро $$$(u, v)$$$.

Гарантируется, что граф $$$G$$$ таков, что суперкомпьютер может загадать описанную выше пару ребер.

Поскольку производитель суперкомпьютеров вашей модели ввел новые квоты на использование оперативной памяти, вы можете сделать не более $$$33$$$ запросов.

Обратите внимание, что интерактор не адаптивный: загаданные ребра $$$e_1$$$ и $$$e_2$$$ фиксированы до начала взаимодействия и не зависят от ваших запросов.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$4 \le n \le 2000$$$, $$$1 \le m \le \min\left(2 \cdot 10^5, \dfrac{n(n-1)}{2}\right)$$$) — количество вершин и ребер в графе $$$G$$$.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — ребро графа $$$G$$$.

Гарантируется, что граф $$$G$$$ двудольный, не содержит кратных ребер, и что существует пара ребер $$$e_1$$$ и $$$e_2$$$ с описанными выше свойствами.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$4 \cdot 10^6$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Протокол взаимодействия

Для каждого набора входных данных сначала считайте граф $$$G$$$ в описанном выше формате, после чего вы можете сделать не более $$$33$$$ запросов двух типов:

  • ? 1 $$$k \; v_1 \; v_2 \; \ldots \; v_k$$$ ($$$1 \le k \le n$$$, все $$$v_i$$$ различны). В ответ вы получите 1, если подграф $$$G'$$$, состоящий только из указанных вершин и ребер $$$G'$$$, их соединяющих, является двудольным, и 0 в противном случае.
  • ? 2 $$$u \; v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$). В ответ вы получите 1, если ребро $$$(u, v)$$$ присутствует в графе $$$G'$$$, и 0 в противном случае.

Чтобы сообщить ответ, выведите одно из загаданных ребер в формате ! $$$u \; v$$$. После этого сразу переходите к следующему набору входных данных. Вывод ответа не считается запросом.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Формат взлома

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$, следующие $$$m$$$ строк содержат ребра графа $$$G$$$ в формате, описанном выше. Каждая из следующих двух строк содержит два целых числа $$$u$$$ и $$$v$$$ — ребра $$$e_1$$$ и $$$e_2$$$. Граф $$$G$$$ и ребра $$$e_1$$$, $$$e_2$$$ должны удовлетворять всем ограничениям и свойствам, описанным выше.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Лог взаимодействия
< 2
< 4 2
< 1 2
< 3 4
> ? 1 3 1 3 4
< 0
> ? 2 1 3
< 1
> ! 1 3
< 5 3
< 1 2
< 2 3
< 4 5
> ? 2 1 4
< 1
> ! 1 4
Примечание

В первом наборе входных данных загаданы рёбра $$$(1, 3)$$$ и $$$(1, 4)$$$. Первый запрос выбирает вершины $$$1$$$, $$$3$$$ и $$$4$$$, которые образуют треугольник в $$$G'$$$, поэтому ответ равен $$$0$$$. Второй запрос подтверждает наличие ребра $$$(1, 3)$$$, и мы сообщаем это загаданное ребро.

Во втором наборе входных данных загаданы рёбра $$$(1, 4)$$$ и $$$(3, 5)$$$. Запрос подтверждает наличие ребра $$$(1, 4)$$$, и мы сообщаем это загаданное ребро.