Это интерактивная задача.
Дан простой неориентированный граф с \(n\) вершинами пронумерованными от \(1\) до \(n\), ваша задача состоит в том, чтобы покрасить все вершины так, чтобы для каждого цвета \(c\), выполнялись следующие условия:
- Множество вершин цвета \(c\) является связным;
- \(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\) такая, что
- \(u_1 = u\), \(v_k = v\), и \(v_i = u_{i+1}\) для любого \(1 \leq i < k\); и
- \(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\)), вы должны вывести
В отдельной строке. Если это
\(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\).
Примечание
В примере только один набор входных данных.
В нем \(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\).