Это интерактивная задача.
Вася обожает решать загадки и разгадывать головоломки. На этот раз он нашел странный прибор и хочет выяснить принцип его работы.
Этот прибор зашифрован с помощью дерева (связного неориентированного графа без циклов), состоящего из \(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\)). Выведенные ребра должны образовывать дерево. Будьте внимательны, лишние пробелы или переводы строк запрещены.