CF2215C Oriented Journey

This is a run-twice (communication) interactive problem. There are two players: Player A (Neri) and Player B (Mashiro). The jury will first interact with Player A. After Player A ends their interaction, the jury will interact with Player B. Note that Player A and Player B may not directly pass information to each other; both players are only able to send information to or receive information from the jury, but they may agree on the strategy they will use to communicate. Before the interaction, the jury determines an undirected tree $ T $ of size $ n $ and an integer $ s $ ( $ 1\le s\le 2^{n-1} $ ). These values are consistent across both players. Player A (Neri) first receives the two integers $ n $ and $ s $ from the jury without acquiring extra information about the tree $ T $ . Then, the jury will interact with Neri for exactly $ n-1 $ rounds. In each round of interaction: - The jury will reveal an undirected edge of $ T $ to Neri, and then Neri needs to assign a direction to it immediately. Note that all $ n-1 $ edges of $ T $ are directed after this interaction, forming a new directed tree $ T' $ . Player B (Mashiro) receives the directed tree $ T' $ created in the interaction between Neri and the jury. Her task is to determine the value of $ s $ according to the information she receives. Neri wants to ensure that Mashiro can determine the integer $ s $ . Your task is to act as both players and determine an optimal interaction strategy for both players so that Mashiro can determine the integer $ s $ correctly. First Run Your code will be run exactly two times on each test. On the first run, you will be Player A (Neri). Input The first line of the input contains two integers $ t $ and $ q $ ( $ 1 \le t \le 10^4 $ , $ q=1 $ ) — the number of test cases and the run number. Here, the purpose of giving $ q=1 $ is so your program recognizes that this is its first run, and it should act as Player A (Neri). For each test case, you should first read two integers $ n $ and $ s $ ( $ 3\le n \le 30 $ , $ 1\le s \le 2^{n-1} $ ) — the size of $ T $ and the integer to deliver. Interaction For each test case, recall that you will first receive $ n $ and $ s $ in the input from the jury according to the input format above. Then, you need to interact with the jury exactly $ n-1 $ times: - First, read two integers $ u $ and $ v $ ( $ 1\le u \lt v\le n $ ) from the jury, denoting that there is an undirected edge $ (u,v) $ in $ T $ ; - Then, print two integers $ a $ and $ b $ on a new line to the jury, separated by a space, where $ (a,b) $ is either $ (u,v) $ or $ (v,u) $ . Printing $ (a,b)=(u,v) $ means you assign the direction $ u\rightarrow v $ , and printing $ (a,b)=(v,u) $ means you assign the direction $ v\rightarrow u $ . Note that you must assign the direction for the current undirected edge before acquiring the information of the next one. After that, you will either proceed to the next test case, or your program must terminate if you have processed every test case. The interactor is not adaptive, which means that the tree $ T $ in each test case is fixed before any interaction. After each round of interaction do not forget to output the end of line and flush $ ^{\text{∗}} $ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $ -1 $ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid interaction or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream. Second Run On the second run, you are Player B (Mashiro). Input The first line of the input contains two integers $ t $ and $ q $ ( $ 1\le t\le 10^4 $ , $ q=2 $ ) — the number of test cases and the run number. Here, the purpose of giving $ q=2 $ is so your program recognizes that this is its second run, and it should act as Player B (Mashiro). The first line of each test case contains a single integer $ n $ ( $ 3\le n \le 30 $ ) — the size of $ T' $ . Then $ n-1 $ lines follow, each containing two integers $ u $ and $ v $ ( $ 1\le u,v\le n $ ), denoting that there is a directed edge $ u\rightarrow v $ in $ T' $ . Note that the test cases in the second run may be shuffled. Please see the example test case for further illustration. Output For each test case, output a single integer $ s $ — the integer you determined from $ T' $ . After this, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict. Then, proceed to the next test case, or terminate your program if it is the last test case. Hacks Hacks are not allowed in this problem. $ ^{\text{∗}} $ To flush, use: - fflush(stdout) or cout.flush() in C++; - sys.stdout.flush() in Python; - see the documentation for other languages.

无

无

第一轮示例：Neri 收到的 $s$ 分别为 $s=21$ 和 $s=59$。根据两方约定的策略，Neri 对树进行了定向。 第二轮示例：请注意两轮的测试用例顺序可能被重排。可参考下列 $T'$ 的可视化图示：  第一组测试用例的 $T'$  第二组测试用例的 $T'$ 测试工具 你可以使用命令行工具在本地进行测试。具体下载方式请见题目所附材料。 使用该工具需安装 Python。在终端使用如下命令启动： - Windows：python treedir\_testing\_tool.py [–quiet] - Linux：python3 treedir\_testing\_tool.py [–quiet] 参数介绍： - -q, –quiet ：该参数可选，加上后测试工具不会打印交互日志。 - data_file ：是你准备的数据文件，需满足如下格式： - 第一行两个整数 $t$ 和 $\text{seed}$ 表示测试用例数量和用于随机打乱顺序的种子，$\text{seed}=0$ 表示不打乱。 - 每组用例第一行 $n, s$，随后 $n-1$ 行每行 $u, v$，表示一条树边。 - program ：你的已编译程序文件名。 - arguments ：为你的程序所需参数。 工具命令最上方有详细说明。 注意事项： - 工具并非与评测机完全一致，判罚可能略有不同。 - 工具会检查文件格式，但不会校验输入是否满足题目限制。 - 工具不会检测你的时间/空间消耗限制。 --- （注：题目描述中的所有 LaTeX 数学公式、代码及格式已完整保留，未做更改。） 由 ChatGPT 5 翻译