P16536 [THUPC 2026 Final] Liuguang Decryption

From the final round of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026). Resources such as the editorial can be found at https://github.com/dapingguo8/THUPC2026-final. > The power network has finally been repaired, and the holographic projector starts up smoothly at last. As the night grows deeper, the holograms in mid-air become more and more colorful and dazzling. When everything is ready, Xiao T and Xiao S officially kick off the night event, inviting everyone to team up and join this carefully prepared light-and-shadow game that tests two-person coordination, called "Liuguang Decryption". > > In the center of the square, beams of light intertwine and slowly gather into a holographic light tree. The light tree consists of several floating light-orb nodes and the flowing-light lines connecting them, forming a pure tree structure. When the game begins, no lines are lit, and the challengers cannot observe any unlit lines. Karuha, who operates the system, will first reveal a mysterious number to one challenger stationed at the console. Then, the flowing-light lines will light up one by one; at the instant each line appears, that challenger must decide the direction of its flow. Meanwhile, the partner standing at the other end of the stage must infer the mysterious number solely from the final directed tree structure. > > As participants of the celebration, Neri and Noir decide to cooperate to complete this challenge.

This problem is a **communication problem**. In this problem, your program will be run twice (the first run is called **Phase 1**, and the second run is called **Phase 2**). In Phase 1, your program will receive the positive integer to be transmitted, and communicate with the interactor to send information to Phase 2. In Phase 2, your program will receive the information sent from Phase 1 from the interactor, and infer the transmitted positive integer from this information. You need to design a strategy for each phase, so that in Phase 2 you can infer the value of this positive integer using the information sent in Phase 1. Note: You cannot directly use information stored in Phase 1 during Phase 2 by storing global variables, etc. For clarity, the roles of the characters in the statement are: - The interactor plays Karuha. - Your program plays Neri in Phase 1. - Your program plays Noir in Phase 2. ### Phase 1 Description For Neri stationed at the console, Karuha, who controls the system, will first give her two positive integers $n, s \ (1 \le s \le 2 ^ {n - 1})$, representing the number of light-orb nodes in the holographic light tree and the mysterious number, respectively. Then, Karuha will light up $n - 1$ flowing-light lines one by one, and Neri must immediately assign a flow direction to each line when it lights up. ### Phase 2 Description For Noir standing at the other end of the main stage, she will observe the final form of the entire holographic light tree filled with flowing light. She needs to infer the mysterious number $s$ that Karuha gave to Neri based on the directions of these lines. Please design a strategy to help Neri and Noir complete this transmission process. ### Interaction Process This problem contains multiple test cases. The first line of input contains two positive integers $T, Q$ $(1\le T \le10^4, Q\in \{1,2\})$, representing the number of test cases and the phase number, respectively. Then follow $T$ test cases: - In Phase 1, $Q=1$. For each test case, you first need to read a line containing two positive integers $n,s$ $(3\le n \le 30,1\le s \le 2^{n-1})$, representing the number of light-orb nodes of the holographic light tree $G$ and the mysterious number to be transmitted. Next, you need to perform the following operations $n-1$ times: - Read a line containing two positive integers $a_i,b_i$ $(1\le a_i < b_i \le n)$, representing an undirected line $(a_i,b_i)$ in $G$ that has lit up. Then, you need to output $a_i,b_i$ in any order on one line. If you output in the order $(a_i,b_i)$, it means you direct this line as $a_i\rightarrow b_i$. If you output in the order $(b_i,a_i)$, it means you direct this line as $b_i\rightarrow a_i$. It is guaranteed that the final form of the holographic light tree $G$ is a tree. In this phase, please note: - You must direct the current undirected line before you can learn the information of the next undirected line. - In Phase 2, $Q=2$. For each test case, you first need to read a line containing one positive integer $n$, representing the number of light-orb nodes in the holographic light tree $G'$ after being directed in Phase 1. Next, you need to read $n-1$ lines. The $i$-th line contains two positive integers $a_i',b_i'$, representing a directed line $(a_i',b_i')$ in $G'$, with direction $a_i'\rightarrow b_i'$. After reading, you need to output one line containing one positive integer $s$, representing the value of the mysterious number $s$ in Phase 1. In this phase, please note: - Within a single test file, the input order of test cases compared to Phase 1 **may be different**. - For the same test case, the order in which edges of $G$ are directed in Phase 1 and the order in which directed edges of $G'$ are given in Phase 2 **may be inconsistent**. - In both phases, the node numbering of $G/G'$ remains unchanged. - You must determine the mysterious number $s$ corresponding to the current test case $G'$ before you can learn the information of the next test case. The interactor is not adaptive. The shape of the holographic light tree $G$ is already determined before the interaction starts, and will not change during the interaction. **Do not forget to flush the output stream after outputting each line.**

N/A

N/A

### Sample In the first run, the input is as in [Sample 1 Input]. The directions chosen by Neri are as in [Sample 1 Output]. Note: The blank lines above are only for easier understanding of the separation between the two test cases. In the actual program output, you do not need to print extra blank lines. After all flowing-light lines in the two test cases are directed, the shapes of the holographic light trees are as follows: :::align{center}   ::: Based on the above output, in the second run, one possible input is as in [Sample 2 Input]. Through **telepathy**, Noir infers that for the first test case in Phase 2, $s=59$, and for the second test case, $s=21$. ### Testing Tool The provided `treedir_testing_tool.py` can help you test the correctness of your program and output the interaction process. When testing, put it in the same folder as your compiled program, and then run the following command in the terminal of that folder: ```bash python3 treedir_testing_tool.py [--quiet] ``` Where: - `-q, --quiet` is an optional argument. If specified, the testing tool will not output the interaction process. - `data_file` is the name of the input file you provide to the testing tool. This file should follow the format below: - The first line contains two non-negative integers $T,seed$, representing the number of test cases and the random seed used to shuffle the order of test cases and the order of edges in the tree. If you set $seed=0$, it means no shuffling is performed. - The format of each test case is the same as the Phase 1 input format. - `program` is the name of your program. - `arguments` are the arguments passed to your program. More details can be found in the source code of the testing tool. Please note: 1. This testing tool is **not exactly the same** as the interactive library implementation used in the actual judging. The result is not guaranteed to be the same as your actual submission, and it is only for debugging reference. 2. The testing tool only checks whether your input matches the format, but **will not check** whether your input satisfies the Constraints ($1\le s \le 2^{n-1}$, $G$ is a tree, etc.). 3. The testing tool will not check whether your program meets the time and memory requirements. Translated by ChatGPT 5