CF1738F.Connectivity Addicts

This is an interactive problem.

Given a simple undirected graph with $n$ vertices numbered from $1$ to $n$, your task is to color all the vertices such that for every color $c$, the following conditions hold:

1. The set of vertices with color $c$ is connected;
2. $s_c \leq n_c^2$, where $n_c$ is the number of vertices with color $c$, and $s_c$ is the sum of degrees of vertices with color $c$.

It can be shown that there always exists a way to color all the vertices such that the above conditions hold.

Initially, you are only given the number $n$ of vertices and the degree of each vertex.

In each query, you can choose a vertex $u$. As a response, you will be given the $k$-th edge incident to $u$, if this is the $k$-th query on vertex $u$.

You are allowed to make at most $n$ queries.

An undirected graph is simple if it does not contain multiple edges or self-loops.

The degree of a vertex is the number of edges incident to it.

A set $S$ of vertices is connected if for every two different vertices $u, v \in S$, there is a path, which only passes through vertices in $S$, that connects $u$ and $v$. That is, there is a sequence of edges $(u_1, v_1), (u_2, v_2), \dots, (u_k, v_k)$ with $k \geq 1$ such that

1. $u_1 = u$, $v_k = v$, and $v_i = u_{i+1}$ for every $1 \leq i \lt k$; and
2. $u_k \in S$ and $v_k \in S$ for every $1 \leq i \leq k$.

Especially, a set containing only one vertex is connected.

Interaction

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The following lines contain the description and the interactive section of each test case.

For each test case, you begin the interaction by reading an integer $n$ ($1\le n \le 1000$) in the first line, indicating the number of vertices in the graph.

The second line contains $n$ integers $d_1, d_2, \dots, d_n$ ($0 \leq d_i \leq n - 1$), where $d_i$ is the degree of vertex $i$.

To make a query on vertex $u$ ($1 \leq u \leq n$), you should output

• "? $u$"

in a separate line. If this is the $k$-th query on vertex $u$, vertex $e_{u, k}$ will be given in the next separate line, where $\left(u, e_{u, k}\right)$ is the $k$-th edge incident to vertex $u$. In case of $k \gt d_u$, define $e_{u, k} = -1$. You should make no more than $n$ "?" queries.

To give the answer, you should output

• "! $c_1$ $c_2$ $\dots$ $c_n$"

in a separate line, where $c_i$ ($1 \leq c_i \leq n$) is the color of vertex $i$. After that, your program should continue to the next test case, or terminate if this is the last test case.

It is guaranteed that the graph is a simple undirected graph.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

In case your query format is invalid, or you have made more than $n$ "?" queries, you will receive Wrong Answer verdict.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hack Format

The first line of the hack contains an integer $t$ ($1 \leq t \leq 1000$), indicating the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 1000$), indicating the number of vertices in the graph.

Then $n$ lines follow. The $i$-th line contains an integer $d_i$ ($0 \leq d_i \leq n - 1$), indicating the degree of vertex $i$, and then $d_i$ distinct integers $e_{i,1}, e_{i,2}, \dots, e_{i,d_i}$ ($1 \leq e_{i, j} \leq n$ and $e_{i,j} \neq i$), where $\left(i, e_{i,j}\right)$ is the $j$-th edge incident to vertex $i$.

It should be guaranteed that the graph is a simple undirected graph.

It should be guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

这是一个交互式问题。

给定一个包含 $n$ 个顶点（编号为 $1$ 到 $n$）的简单无向图，你的任务是为所有顶点染色，使得对每种颜色 $c$，以下条件均成立：

1. 颜色为 $c$ 的顶点集合是连通的；
2. $s_c \leq n_c^2$，其中 $n_c$ 表示颜色为 $c$ 的顶点数，$s_c$ 表示颜色为 $c$ 的所有顶点的度数之和。

可以证明，总存在一种染色方案满足上述条件。

初始时，你仅被给定顶点数 $n$ 以及每个顶点的度数。

每次查询中，你可以选择一个顶点 $u$。作为响应，若这是你在顶点 $u$ 上进行的第 $k$ 次查询，则你会得到与 $u$ 相连的第 $k$ 条边。

你最多可进行 $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$，且对每个 $1 \leq i < k$，有 $v_i = u_{i+1}$；
2. 对每个 $1 \leq i \leq k$，均有 $u_i \in S$ 且 $v_i \in S$。

特别地，仅含一个顶点的集合是连通的。

交互方式

每个测试包含多个测试用例。第一行是一个整数 $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$"

若这是你在顶点 $u$ 上进行的第 $k$ 次查询，则下一行将给出顶点 $e_{u, k}$，其中 $\left(u, e_{u, k}\right)$ 是与顶点 $u$ 相连的第 $k$ 条边。若 $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$ 次，你将收到“Wrong Answer”判据。

每次输出查询后，请务必输出换行符并刷新输出缓冲区。否则，你将收到“Idleness limit exceeded”。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• 其他语言请参考相应文档。

Hack 输入格式

Hack 输入的第一行是一个整数 $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)$ 是与顶点 $i$ 相连的第 $j$ 条边。

需保证该图是一个简单无向图。

需保证所有测试用例的 $n$ 值之和不超过 $1000$。

In the example, there is only one test case.

In the test case, there are $n = 5$ vertices with vertices $1, 2, 3, 4$ of degree $2$ and vertex $5$ of degree $0$. It is obvious that vertex $5$ is isolated, i.e., it does not connect to any other vertices.

A possible interaction is shown in the sample input and output, where $4$ "?" queries are made on vertex $1$ twice and vertex $3$ twice. According to the responses to these queries, we know that each of vertex $1$ and vertex $3$ connects to two vertices $2$ and $4$.

A possible solution is shown in the sample output, where vertex $1$ and vertex $2$ are colored by $1$, vertex $3$ and vertex $4$ are colored by $2$, and vertex $5$ is colored by $3$. It can be seen that this solution satisfies the required conditions as follows.

• For color $c = 1$, vertex $1$ and vertex $2$ are connected. Moreover, $n_1 = 2$ and $s_1 = d_1 + d_2 = 2 + 2 = 4 \leq n_1^2 = 2^2 = 4$;
• For color $c = 2$, vertex $3$ and vertex $4$ are connected. Moreover, $n_2 = 2$ and $s_2 = d_3 + d_4 = 2 + 2 = 4 \leq n_2^2 = 2^2 = 4$;
• For color $c = 3$, there is only one vertex (vertex $5$) colored by $3$. Moreover, $n_3 = 1$ and $s_3 = d_5 = 0 \leq n_3^2 = 1^2 = 1$.

在该示例中，仅有一个测试用例。

在该测试用例中，共有 $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$。