F. Connectivity Addicts
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: The set of vertices with color \(c\) is connected; \(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 \(u_1 = u\), \(v_k = v\), and \(v_i = u_{i+1}\) for every \(1 \leq i < k\); and \(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.
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\).