Это интерактивная задача.
Мадлен играет с бесполезной машиной.
Бесполезная машина имеет скрытое дерево размером $$$n$$$, и Мадлен должна определить ребра дерева, задавая вопросы машине.
В запросе Мадлен передаст машине перестановку $$$p$$$ из $$$[1,2,\ldots,n]$$$, и машина вернет последовательность $$$q_1, q_2, \ldots, q_n$$$, где $$$q_i$$$ — это количество рёбер индуцированного подграфа, образованного на вершинах $$$\{p_1,p_2,\ldots,p_i\}$$$.
Здесь индуцированный подграф графа $$$G(V,E)$$$, образованный подмножеством вершин $$$V' \subseteq V$$$, это граф, состоящий из вершин данного множества и всеми ребрами между ними, которые существовали в исходном графе $$$G$$$.
Однако машина работает медленно, поэтому Мадлен может получить результаты только после завершения всех запросов. Память этой машины тоже не очень велика, поэтому Мадлен может задать только $$$31$$$ вопрос. Она не знает, как это решить, поэтому пригласила вас помочь ей.
Обратите внимание, что интерактор не адаптивен. Это значит, что дерево зафиксировано заранее и не меняется от ваших запросов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3\le n\le 5\cdot 10^4$$$) — размер дерева.
Гарантируется, что сумма $$$n$$$ по всем набора не превышает $$$5\cdot 10^4$$$.
Взаимодействие начинается с чтения целого числа $$$n$$$.
Затем выведите одно целое число $$$k$$$ ($$$1 \leq k \leq 31$$$) — количество запросов.
Чтобы задать запрос, выведите строку в следующем формате:
После того как вы задали все $$$k$$$ запросов, прочитайте $$$k$$$ строк по $$$n$$$ целых чисел $$$q_{i,j}$$$ — ответы на запросы, как описано выше.
Когда вы узнаете скрытое дерево, выведите $$$n-1$$$ строк в следующем формате:
Затем переходите к следующему набору входных данных или завершите программу, если больше нет наборов.
После вывода всех $$$k$$$ запросов не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».
На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.
Взломы
Чтобы совершить взлом, используйте следующий формат.
Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$).
Первая строка каждого набора входных данных должна содержать одно число $$$n$$$ ($$$3 \le n \le 5\cdot 10^4$$$).
$$$i$$$-я из следующих $$$n - 1$$$ строк должна содержать два числа $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$).
Данные ребра должны формировать дерево.
Сумма $$$n$$$ по всем наборам не должна превышать $$$5 \cdot 10^4$$$.
$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:
3 3 0 1 2 0 0 2 4 0 1 1 3 0 1 1 3 0 1 2 3 5 0 0 1 3 4
2 1 2 3 1 3 2 1 2 2 3 3 3 2 4 1 1 4 3 2 1 2 3 4 2 3 1 2 4 1 1 1 2 3 4 5 1 4 4 3 3 2 5 3
Для первого набора входных данных:
Для третьего набора:
