P17449 Nailoong vs. Bombloong 3.2 / Nailoong vs. Bombloong 3.2.

**This is a communication problem.** In this problem, your program will be run twice. Between the two runs, all variables stored in memory will be lost, but the information obtained in the first run may be very important for solving the problem correctly in the second run. There are two roles in this problem: “Nailoong” and “Bombloong”. Nailoong has the complete structure of a tree with $n$ nodes, while Bombloong only knows the number of nodes $n$. Since Bombloong is locked up by an evil little leopard, Nailoong can only use a special one-way communication method to help Bombloong reconstruct a tree that is **isomorphic** to the original tree. **Isomorphic:** Two trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$ are isomorphic if and only if there exists a bijection $f:V_1\to V_2$ such that for all $\{u,v\}\in E_1$, $\{f(u),f(v)\}\in E_2$. The communication rules are as follows: - Nailoong needs to color each node of the tree either black or white. - The little leopard will generate a sequence according to the following code. - Nailoong can only send this sequence $c_1,c_2,\ldots,c_{2n-1}$ of length $2n-1$ to Bombloong.  Nailoong cannot directly send the node labels to Bombloong; she can only send the sequence $c$. After receiving $n$ and the sequence $c$, Bombloong needs to construct and output a tree that is isomorphic to Nailoong’s tree. ### Communication Protocol For each test point, the contestant’s program will be run twice. In the provided files, there is a testing tool for local debugging. #### First Run In the first run, you will play the role of “Nailoong”. **Input** The first line contains a string `first`, which allows your program to recognize that this is the first run. The second line contains an integer $T$ ($1\le T\le 10^4$), the number of test cases. For each test case, the first line contains an integer $n$ ($2\le n\le 2\times 10^5$), the number of nodes in the tree. The next $n-1$ lines each contain two integers $u,v$ ($1\le u,v\le n$), representing an edge of the tree. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$. **Output** Your output should contain $T$ lines. The $i$-th line contains a sequence $col_1,col_2,\ldots,col_n$ whose length equals the number of nodes $n$ of the $i$-th tree ($col_i\in\{0,1\}$, $i=1,2,\ldots,n$), meaning Nailoong colors the $i$-th node with $col_i$. Here, $col_i=0$ means white, and $col_i=1$ means black. #### Second Run In the second run, you will play the role of “Bombloong”. **Input** The first line contains a string `second`, which allows your program to recognize that this is the second run. The second line contains an integer $T$ ($1\le T\le 10^4$), the number of test cases. For each test case, the first line contains an integer $n$ ($2\le n\le 2\times 10^5$), the number of nodes in the tree. The next line contains $2n-1$ integers, representing the sequence generated by the judge based on Nailoong’s coloring. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$. **Output** For the $i$-th test case, let the input number of nodes be $n$. Output $n-1$ lines, each containing two integers $u,v$, representing an edge of the tree you reconstructed ($1\le u,v\le n$). You need to ensure that the tree you output is isomorphic to the tree given in the first run.

See the communication protocol in the problem description.

See the communication protocol in the problem description.

The two samples demonstrate the two runs in the same test point. Note that if the trees in the first input are $t_1,\ldots,t_T$ in order, and the output color sequences are $col_1,\ldots,col_T$. Let the color sequences obtained by the judge from $t_i,col_i$ ($1\le i\le T$) be $a_i$. The judge will randomly generate a permutation $p_1,\ldots,p_T$ of $1\sim T$, and then the order sent to the second input will be $a_{p_1},\ldots,a_{p_T}$. Let the output trees be $t'_1,t'_2,\ldots,t'_T$ in order; the judge will compare $t_{p_i}$ and $t'_i$ to judge correctness. ### How to Use the Provided Files ```batch python3 tree_communication_testing_tool2.py data.in ./solution python3 tree_communication_testing_tool2.py --trials 10 data.in ./solution python3 tree_communication_testing_tool2.py data.in python3 solution.py ``` Here, `solution` or `solution.py` is the executable compiled from C/C++ or the Python source code, `data.in` is the data for the first input, and the `trials` parameter indicates the number of repeated tests. Translated by ChatGPT 5