C2. Интерактивный граф (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вы можете спросить не более $$$n + m$$$ вопросов, а также $$$n \leq 30$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

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

Жюри загадало ориентированный ацикличный граф без петель и кратных рёбер, в котором $$$n$$$ вершин и $$$m$$$ рёбер.

Ваша задача определить, какие рёбра содержит этот граф. Для этого вы можете задавать вопросы вида: как выглядит $$$k$$$-й путь в лексикографически$$$^{\text{∗}}$$$ отсортированном по возрастанию списке всех путей графа.

Путь в графе это последовательность вершин $$$u_{1}, u_{2}, \dots, u_{l}$$$, такая, что для любого $$$i \lt l$$$ в графе существует ребро ($$$u_{i}, u_{i + 1}$$$).

Ваша задача справиться с этим, задав не более $$$n + m$$$ вопросов.

$$$^{\text{∗}}$$$Последовательность $$$a$$$ лексикографически меньше последовательности $$$b$$$, если и только если выполняется одно из следующего:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$; или
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в последовательности $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

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

Каждый набор входных данных состоит из одной строки с целым числом $$$n$$$ ($$$1 \le n \le 30$$$) — количество вершин в графе.

Жюри гарантирует, что загаданный граф не содержит циклов и кратных рёбер.

Обратите внимание, что $$$m$$$ вам неизвестно!

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

Взаимодействие каждого набора данных начинается с чтения целого числа $$$n$$$.

Затем вы можете задать до $$$n + m$$$ вопросов.

Чтобы задать вопрос, выведите строку в формате «? k» (без кавычек) ($$$1 \le k \le 2^{30}$$$). После каждого вопроса считайте целое число $$$q$$$ — количество вершин в $$$k$$$-м пути. Далее, если $$$q = 0$$$, то не существует такого пути, иначе считайте $$$q$$$ целых чисел — номера вершин, из которых состоит этот путь.

Можно показать, что при заданных ограничениях количество различных путей в графе не превосходит $$$2^{30}$$$.

Чтобы сообщить ответ, сначала выведите строку в формате «! m», а затем выведите $$$m$$$ строк с описанием рёбер в формате «u v», что означает, что существует ребро, которое ведет из $$$u$$$ в $$$v$$$. Вы можете выводить рёбра в любом порядке. Вывод ответа не считается запросом.

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

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

Взломы:

Для взломов используйте следующий формат:

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

Первая строка каждого набора должна содержать два целых числа $$$n, m$$$ ($$$1 \leq n \leq 30$$$, $$$0 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$) — количество вершин и рёбер в графе.

Следующие $$$m$$$ строк должны содержать описания рёбер. Каждое ребро задается двумя целыми числами $$$v$$$, $$$u$$$ ($$$1 \leq v, u \leq n$$$, $$$v \neq u$$$), означающее ребро из вершины $$$v$$$ в вершину $$$u$$$.

Граф не может содержать циклов и кратные рёбра.

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

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
3
5

1 1

2 1 2

3 1 2 4

3 1 2 5

2 1 3

3 1 3 4

3 1 3 5

1 2

1 3

1 4

1 5

1

0

2

1 1

1 2

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


? 1

? 2

? 3

? 4

? 5

? 6

? 7

? 8

? 11

? 14

? 15

! 6
1 3
1 2
2 4
3 4
2 5
3 5

? 2

! 0

? 1

? 2

? 3

! 1
2 1
Примечание

Граф для первого набора входных данных.

В этом графе $$$15$$$ путей, в лексикографическом порядке они располагаются следующим образом:

  • $$$1$$$
  • $$$1 \to 2$$$
  • $$$1 \to 2 \to 4$$$
  • $$$1 \to 2 \to 5$$$
  • $$$1 \to 3$$$
  • $$$1 \to 3 \to 4$$$
  • $$$1 \to 3 \to 5$$$
  • $$$2$$$
  • $$$2 \to 4$$$
  • $$$2 \to 5$$$
  • $$$3$$$
  • $$$3 \to 4$$$
  • $$$3 \to 5$$$
  • $$$4$$$
  • $$$5$$$