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

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

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

Этот прибор зашифрован с помощью дерева (связного неориентированного графа без циклов), состоящего из $$$n$$$ вершин, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Чтобы решить головоломку надо угадать это дерево.

К счастью прибор умеет выполнять одну операцию, исходя из которой надо разгадать его шифр. Можно ввести в прибор последовательность $$$d_1, d_2, \ldots, d_n$$$ целых неотрицательных чисел. На приборе есть $$$n$$$ лампочек, $$$i$$$-я из которых отвечает за $$$i$$$-ю вершину дерева-шифра. Для всех $$$i$$$ из этих лампочек $$$i$$$-я загорится, если существует такая вершина дерева-шифра с номером $$$j \neq i$$$, что $$$dist(i, j) \leq d_j$$$. Здесь $$$dist(i, j)$$$ обозначает расстояние между вершинами $$$i$$$ и $$$j$$$ в дереве-шифре, то есть количество ребер в простом пути между вершинами $$$i$$$ и $$$j$$$.

Вася хочет за $$$\leq 80$$$ операций с прибором решить головоломку и угадать дерево-шифр. Помогите ему!

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

В начале вашей программе вводится единственное целое число $$$n$$$ — количество вершин в дереве-шифре прибора ($$$2 \leq n \leq 1000$$$).

Далее вы можете выполнять операции в следующем формате. Сначала выведите символ "?" (без кавычек) и за ним $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$, разделенных пробелами. Заметьте, что в операциях для всех $$$i$$$ должно быть выполнено неравенство $$$0 \leq d_i < n$$$. В ответ будет выведена строка $$$s$$$ длины $$$n$$$, состоящая из символов "0" и "1" (без кавычек). Для всех $$$i$$$ символ $$$s_i$$$ будет равен "0", если у прибора не включилась лампочка, соответствующая $$$i$$$-й вершине дерева-шифра и "1", иначе.

После нескольких запросов вы должны вывести угаданное дерево. Для этого в первой строке выведите единственный символ "!" (без кавычек). В следующих $$$n-1$$$ строках выведите по $$$2$$$ целых числа $$$a_i$$$, $$$b_i$$$ — номера вершин, соединяющих $$$i$$$-е ребро дерева. Выведенные числа должны удовлетворять условиям $$$1 \leq a_i, b_i \leq n$$$ и $$$a_i \neq b_i$$$. Эти ребра должны образовывать дерево, совпадающее с загаданным. Выводить ребра можно в любом порядке. После этого ваша программа должна завершиться.

Гарантируется, что в каждом тесте дерево-шифр будет зафиксировано заранее и не будет меняться в зависимости от выполняемых операций.

Ваша программа может выполнить от $$$0$$$ до $$$80$$$ операций с прибором и после этого сообщить дерево, совпадающее с загаданным.

Если ваша программа сделает больше $$$80$$$ операций, то она может получить любой вердикт, потому что будет считывать данные из закрытого потока ввода. Также, если ваша программа сделает операцию или выведет ответ в неверном формате, она может получить любой вердикт. Будьте внимательны.

Не забудьте сбрасывать буфер вывода после того, как выведете данные для операции или ответ.

Чтобы сбросить буфер вывода вы можете использовать:

  • fflush(stdout) в C++.
  • System.out.flush() в Java.
  • stdout.flush() в Python.
  • flush(output) в Pascal.
  • Прибегните к документации других языков.

Взломы:

Первая строка должна содержать единственное целое число $$$n$$$ — количество вершин в дереве-шифре ($$$2 \leq n \leq 1000$$$). Следующая $$$n-1$$$ строка должна содержать по $$$2$$$ целых числа $$$a_i$$$, $$$b_i$$$ — номера вершин, соединяющих $$$i$$$-е ребро дерева ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$). Выведенные ребра должны образовывать дерево. Будьте внимательны, лишние пробелы или переводы строк запрещены.

Пример
Входные данные
5
00000
11011
11100
10010
Выходные данные
? 0 0 0 0 0
? 1 1 2 0 2
? 0 0 0 1 0
? 0 1 0 0 1
!
4 2
1 5
3 4
4 1
Примечание

Дерево-шифр из первого теста выглядит так:

Таблица попарных расстояний между вершинами выглядит так:

  • Если сделать операцию, в которой $$$d = [0, 0, 0, 0, 0]$$$, то ни одна лампочка не загорится, потому что $$$dist(i, j) > 0$$$ при всех $$$i \neq j$$$.
  • Если сделать операцию, в которой $$$d = [1, 1, 2, 0, 2]$$$, то загорятся все лампочки, кроме лампочки, соответсвующей вершине дерева-шифра с номером $$$3$$$. Например, лампочка, соответсвующая вершине с номером $$$1$$$ загорится, потому что $$$dist(1, 5) = 1 \leq 2 = d_5$$$.
  • Если сделать операцию, в которой $$$d = [0, 0, 0, 1, 0]$$$, то загорятся все лампочки, кроме лампочек, соответсвующих вершинам дерева-шифра с номерами $$$4$$$ и $$$5$$$.
  • Если сделать операцию, в которой $$$d = [0, 1, 0, 0, 1]$$$, то загорятся только лампочки, соответсвующие вершинам дерева-шифра с номерами $$$1$$$ и $$$4$$$.