1738F · Connectivity Addicts

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

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