F. Упоротая связность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Дан простой неориентированный граф с $$$n$$$ вершинами пронумерованными от $$$1$$$ до $$$n$$$, ваша задача состоит в том, чтобы покрасить все вершины так, чтобы для каждого цвета $$$c$$$, выполнялись следующие условия:

  1. Множество вершин цвета $$$c$$$ является связным;
  2. $$$s_c \leq n_c^2$$$, где $$$n_c$$$ число вершин цвета $$$c$$$, и $$$s_c$$$ сумма степеней вершин цвета $$$c$$$.
Можно показать, что всегда существует раскраска такая, что условия выполняются.

Исходно вам дано только $$$n$$$ - число вершин и степень каждой вершины.

Каждым запросом вы можете выбрать вершину $$$u$$$. В ответ вы получите $$$k$$$-е ребро, исходящее из $$$u$$$, если это $$$k$$$-й запрос к вершине $$$u$$$.

Вы можете сделать максимум $$$n$$$ запросов.

Неориентированный граф называется простым, если он не содержит кратных ребер и петель.

Степень вершины это число ребер, исходящих из нее.

Множество вершин $$$S$$$ называется связным если для любых двух различных вершин $$$u, v \in S$$$, существует путь, который проходит только по вершинам множества $$$S$$$, и соединяет $$$u$$$ и $$$v$$$. Формально, существует последовательность ребер $$$(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$$$ с $$$k \geq 1$$$ такая, что

  1. $$$u_1 = u$$$, $$$v_k = v$$$, и $$$v_i = u_{i+1}$$$ для любого $$$1 \leq i < k$$$; и
  2. $$$u_k \in S$$$ и $$$v_k \in S$$$ для любого $$$1 \leq i \leq k$$$.
Множество содержащее одну вершину является связным.
Протокол взаимодействия

Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Следующие строки содержат описание и интерактивную часть каждого набора входных данных.

Для каждого набора входных данных вы начинаете взаимодействие с итерактором с чтения целого числа $$$n$$$ ($$$1\le n \le 1000$$$) в первой строке, означающего число вершин в графе.

Вторая строка содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$0 \leq d_i \leq n - 1$$$), где $$$d_i$$$ это степень вершины $$$i$$$.

Чтобы совершить запрос к вершине $$$u$$$ ($$$1 \leq u \leq n$$$), вы должны вывести

  • «? $$$u$$$»
В отдельной строке. Если это $$$k$$$-й запрос к вершине $$$u$$$, вершина $$$e_{u, k}$$$ будет выведена на следующей отдельной строке, где $$$\left(u, e_{u, k}\right)$$$ это $$$k$$$-е ребро, исходящее из вершины $$$u$$$. В случае если $$$k > d_u$$$, положим $$$e_{u, k} = -1$$$. Вы должны сделать не более $$$n$$$ «?» запросов.

Чтобы дать ответ вы должны вывести

  • «! $$$c_1$$$ $$$c_2$$$ $$$\dots$$$ $$$c_n$$$»
в отдельной строке, где $$$c_i$$$ ($$$1 \leq c_i \leq n$$$) это цвет вершины $$$i$$$. После этого ваша программа должны продолжить работать со следующим набором входных данных или завершиться, если это был последний.

Гарантируется, что дан простой неориентированный граф.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

В случае, если формат запроса неверный, или вы сделали более $$$n$$$ «?» запросов, вы получите вердикт Неправильный Ответ.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

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

Первая строка взлома должна содержать целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$), означающее число наборов входных данных. Следующие строки содержат описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 1000$$$), означающее число вершин в графе.

Затем следуют $$$n$$$ строк. В $$$i$$$-й строке содержится целое число $$$d_i$$$ ($$$0 \leq d_i \leq n - 1$$$), означающее степень вершины $$$i$$$, и затем $$$d_i$$$ различных целых чисел $$$e_{i,1}, e_{i,2}, \dots, e_{i,d_i}$$$ ($$$1 \leq e_{i, j} \leq n$$$ и $$$e_{i,j} \neq i$$$), где $$$\left(i, e_{i,j}\right)$$$ это $$$j$$$-е ребро, исходящее из вершины $$$i$$$.

Вы должны гарантировать, что граф является простым и неориентированным.

Вы должны гарантировать, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.

Пример
Входные данные
1
5
2 2 2 2 0

2

4

2

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



? 1

? 1

? 3

? 3

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

В примере только один набор входных данных.

В нем $$$n = 5$$$ вершин, из которых $$$1, 2, 3, 4$$$ имеют степень $$$2$$$ и вершина $$$5$$$ имеет степень $$$0$$$. Это означает, что вершина $$$5$$$ изолированная - не соединена ни с одной другой вершиной.

Возможное взаимодействие с итерактором показано во вводе и выводе примера, использовано $$$4$$$ «?» запроса. Из них два к вершине $$$1$$$ и два к вершине $$$3$$$. Исходя из результатов этих запросов мы знаем, что вершины $$$1$$$ и $$$3$$$ соединены с вершинами $$$2$$$ и $$$4$$$.

Возможное решение показано, вершины $$$1$$$ и $$$2$$$ покрашены в цвет $$$1$$$, вершины $$$3$$$ и $$$4$$$ покрашены в цвет $$$2$$$, и вершина $$$5$$$ покрашена в цвет $$$3$$$. Легко заметить, что решение удовлетворяет условиям.

  • Для цвета $$$c = 1$$$, вершины $$$1$$$ и $$$2$$$ связны. Также, $$$n_1 = 2$$$ и $$$s_1 = d_1 + d_2 = 2 + 2 = 4 \leq n_1^2 = 2^2 = 4$$$;
  • Для цвета $$$c = 2$$$, вершины $$$3$$$ и $$$4$$$ связны. Также, $$$n_2 = 2$$$ и $$$s_2 = d_3 + d_4 = 2 + 2 = 4 \leq n_2^2 = 2^2 = 4$$$;
  • Для цвета $$$c = 3$$$, есть только одна вершина (вершина $$$5$$$) покрашенная в цвет $$$3$$$. Также, $$$n_3 = 1$$$ и $$$s_3 = d_5 = 0 \leq n_3^2 = 1^2 = 1$$$.