P17501 [ICPC 2026 Wuhan I] Nailoong vs. Bombloong 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 crucial for correctly solving the problem in the second run. There are two characters in this problem: “Nailoong” and “Bombloong”. Nailoong has the complete structural information of a tree with $n$ nodes, while Bombloong only knows the number of nodes $n$. Since Bombloong has been imprisoned by the evil Little Leopard, Nailoong can only help Bombloong reconstruct a tree that is isomorphic to the original tree through a special one-way communication method. The rules of communication are as follows: - Initially, all nodes in the tree are white. - Nailoong can perform $m \le n-3$ operations (the value of $m$ is determined by Nailoong). - In the $i$-th operation, Nailoong needs to choose a node $x_i$ on the tree and flip its color (white to black, black to white). - After each flip, let $a_i$ be the number of edges in the current tree whose two endpoints have different colors. - After $m$ operations, Nailoong obtains a sequence $a_1,a_2,\cdots,a_m$ of length $m$. Nailoong cannot directly send node indices to Bombloong; she can only send the total number of operations $m$ and the sequence $a$ to Bombloong. After receiving $n$, $m$, and the sequence $a$, Bombloong needs to construct and output a tree that is isomorphic to Nailoong's tree. ## Communication Protocol In each test case, the contestant's program will be run twice. A testing tool is provided in the handout files for local debugging. ## First Run In the first run, you will play the role of “Nailoong”. ### Input The first line of input contains an integer $1$, which allows your program to identify that this is the first run. The second line contains an integer $n$ ($4 \le n \le 3\times10^5$), representing 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 in the tree. ### Output The first line of output should contain an integer $m$ ($0 \le m \le n-3$), representing the number of operations. The second line contains $m$ integers $x_1,x_2,\cdots,x_m$ ($1 \le x_i \le n$), representing the indices of the nodes flipped by Nailoong in each operation in sequence. ## Second Run In the second run, you will play the role of “Bombloong”. ### Input The first line of input contains an integer $2$, which allows your program to identify that this is the second run. The second line contains two integers $n,m$ ($4 \le n \le 3\times10^5$, $0 \le m \le n-3$), representing the number of nodes and the number of operations performed by Nailoong, respectively. If $m>0$, the third line contains $m$ integers $a_1,a_2,\cdots,a_m$ ($0 \le a_i \le n$), representing the sequence generated by the judge based on Nailoong's operations; if $m=0$, the third line does not exist. ### Output 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 must ensure that the output tree is isomorphic to the tree provided in the input of the first run. ### First Run #### standard input ```text 1 4 1 2 2 3 3 4 ``` #### standard output ```text 1 2 ``` ### Second Run #### standard input ```text 2 4 1 2 ``` #### standard output ```text 1 3 3 2 2 4 ```

N/A

N/A

The two samples demonstrate the two runs within the same test case. Nailoong flipped node $2$. At this point, the number of edges with different colored endpoints is $2$, so $a_1=2$. Bombloong received the sequence $a=[2]$. Since Bombloong and Nailoong share a deep connection, she immediately guessed the structure of the tree. Although the tree obtained by Bombloong differs from the tree Nailoong held in terms of node indexing, they are isomorphic, so it is still considered correct.