Connectivity Addicts
Contest: Codeforces Global Round 22
Difficulty rating: 2400
Tags: constructive algorithms, dsu, graphs, greedy, interactive, shortest paths, trees

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$$$.

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 < k$$$; and
2. $$$u_k \in S$$$ and $$$v_k \in S$$$ for every $$$1 \leq i \leq k$$$.

Interaction format:
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$$$"

To give the answer, you should output

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

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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
1
5
2 2 2 2 0

2

4

2

4

Example output:
? 1

? 1

? 3

? 3

! 1 1 2 2 3

Editorial:
Let's consider the following BFS-like algorithm.
• Repeat the following procedure until all vertices are visited.   Choose an unvisited vertex $$$u$$$ with the largest degree. Let $$$S$$$ be a set of vertices, initially consisting of the only vertex $$$u$$$.  For every neighbor vertex $$$v$$$ of vertex $$$u$$$,   If vertex $$$v$$$ is visited, color all vertices in $$$S$$$ with the same color as vertex $$$v$$$, and then end the procedure this time;  Otherwise, add vertex $$$v$$$ to set $$$S$$$.   Color all vertices in $$$S$$$ with a new one color.
• Choose an unvisited vertex $$$u$$$ with the largest degree. Let $$$S$$$ be a set of vertices, initially consisting of the only vertex $$$u$$$.
• For every neighbor vertex $$$v$$$ of vertex $$$u$$$,   If vertex $$$v$$$ is visited, color all vertices in $$$S$$$ with the same color as vertex $$$v$$$, and then end the procedure this time;  Otherwise, add vertex $$$v$$$ to set $$$S$$$.
• If vertex $$$v$$$ is visited, color all vertices in $$$S$$$ with the same color as vertex $$$v$$$, and then end the procedure this time;
• Otherwise, add vertex $$$v$$$ to set $$$S$$$.
• Color all vertices in $$$S$$$ with a new one color.
It is clear that in each repetition of the procedure, the number $$$k$$$ of edges visited (i.e., the number of queries) will cause at least $$$k$$$ vertices being colored. Since all vertices will be colored exactly once eventually, the number of queries is no more than $$$n$$$. A careful analysis will find that the number of queries is no more than $$$n-C$$$, where $$$C$$$ is the number of different existing colors.
The time complexity of this algorithm can be $$$O(n)$$$, $$$O(n\log n)$$$, or $$$O(n^2)$$$, depending on concrete implementations. Anyway, any implementation of such time complexity can pass.
It is clear that all vertices with the same color are connected. It remains to see why this algorithm will color all vertices such that $$$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$$$. To see this, it can be shown by induction that after every repetition of the procedure, the number $$$n_c$$$ of vertices with an existing color $$$c$$$ is always no less than the degree of any vertex with color $$$c$$$. Since we enumerate vertices in decreasing order of their degrees, the degree $$$d_u$$$ of the current vertex $$$u$$$ must hold that $$$d_u \leq n_c$$$ for every existing color $$$c$$$. We consider two cases:
• During the procedure, no neighbor vertex $$$v$$$ of vertex $$$u$$$ is visited. That is, every neighbor vertex of vertex $$$u$$$ has degree $$$\leq d_u$$$. Then, there are $$$d_u + 1$$$ vertices in $$$S$$$, and they are assigned with a new color $$$c$$$, thereby $$$s_c \leq (d_u+1) d_u \leq (d_u+1)^2 = n_c^2$$$.
• During the procedure, we find a neighbor vertex $$$v$$$ of vertex $$$u$$$ that is visited. Let $$$c$$$ be the color of vertex $$$v$$$ and $$$n'_c$$$ be the number of vertices with color $$$c$$$ before coloring all vertices in $$$S$$$. We have $$$|S| \leq d \leq n'_c$$$. Let $$$n_c = n'_c+|S|$$$ be the number of vertices with color $$$c$$$ after coloring all vertices in $$$S$$$ with color $$$c$$$. Then $$$s_c \leq s'_c + |S|d \leq (n'_c)^2 + |S|n'_c \leq (n'_c+|S|)^2 = n_c^2$$$.
This interesting problem surprisingly comes from non-traditional algorithm scenarios — QUANTUM algorithms.
Further reading: Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310-1328, 2006.