题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。

题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。

供电网络修复完毕，全息投影仪终于顺利启动。随着夜色渐深，半空中的全息投影愈发缤纷绚丽。一切就绪后，小 T 和小 S 正式拉开了夜间活动的帷幕，邀请大家结伴，共同参与这场精心筹备、考验双人合作默契的光影游戏"流光解密"。

广场中央的光束交织在一起，缓缓汇聚成一棵全息光树。光树由若干个悬浮的光团结点与连接它们的流光线路组成，呈现出纯粹的树形结构。游戏开始时，所有线路均未点亮，挑战者无法观测到任何未点亮的线路。执行系统操作的 Karuha 会率先向驻守在控制台前的一名挑战者揭示一个神秘数字。随后，各条流光线路会逐一亮起，该挑战者必须在每条线路浮现的瞬间，决定其流动的方向；而站在舞台另一端的搭档，则需仅凭最终形成的有向树结构，准确推断出这个神秘数字。

作为庆典参与者，Neri 和 Noir 决定配合完成这项挑战。

题目描述

本题为通信题。

在本题中，你的程序将会被运行两次（以下第一次运行简称为阶段一，第二次运行简称为阶段二）。

在阶段一中你的程序会收到待传递的正整数，并通过与交互器进行交互从而向阶段二传递信息；而在阶段二中你的程序会从交互器收到来自阶段一的信息，并根据这些信息推断出传递的正整数。

你需要为两个阶段分别制定一种策略，使得在阶段二中可以根据阶段一传递出的信息推断出这个正整数的值。

注意：你无法通过存储全局变量等方式在阶段二中直接使用阶段一中存储的信息。

为便于辨认，题面描述中人物名的代表关系如下：

• 交互器扮演 Karuha；
• 你的程序在阶段一中扮演 Neri；
• 你的程序在阶段二中扮演 Noir；

阶段一描述

对于驻守在控制台前的 Neri，掌控系统的 Karuha 首先会向她给出两个正整数 $n, s \ (1 \le s \le 2 ^ {n - 1})$，分别表示全息光树包含的光团数量与神秘数字。

随后，Karuha 将依次点亮 $n - 1$ 条流光线路，Neri 必须在每条线路亮起时，立即为其指定流动的方向。

阶段二描述

对于站在主舞台另一端的 Noir，她将观察到整棵全息光树充满流光的最终形态。她需要根据这些线路的流动方向，推断出 Karuha 赋予给 Neri 的神秘数字 $s$。

请制定策略，帮助 Neri 和 Noir 完成这一传递过程。

交互过程

本题包含多组测试数据。

输入的第一行包含两个正整数 $T, Q$ $(1\le T \le10^4, Q\in \{1,2\})$，分别代表数据组数与阶段编号。

接下来 $T$ 组数据：

• 阶段一中 $Q=1$，此时对于每组数据，你需要先读入一行两个正整数 $n,s$ $(3\le n \le 30,1\le s \le 2^{n-1})$，分别代表全息光树 $G$ 的光团数量与待传递的神秘数字。

  接下来你需要执行以下操作 $n-1$ 次：

  • 读入一行两个正整数 $a_i,b_i$ $(1\le a_i < b_i \le n)$，代表 $G$ 中亮起的一条无向线路 $(a_i,b_i)$；

    然后，你需要将 $a_i,b_i$ 以任意顺序在一行内输出。如果你按照 $(a_i,b_i)$ 的顺序输出，则代表将这条线路定向为 $a_i\rightarrow b_i$；如果你按照 $(b_i,a_i)$ 的顺序输出，则代表将这条线路定向为 $b_i\rightarrow a_i$。

  保证全息光树 $G$ 的最终形态是一棵树。

  在本阶段中，请注意：

  • 你必须为当前无向线路定向后才能得知下一条无向线路的信息。

• 阶段二中 $Q=2$，此时对于每组数据，你需要先读入一行一个正整数 $n$，代表阶段一中定向后全息光树 $G'$ 的光团数量。

  接下来你需要读入 $n-1$ 行，第 $i$ 行包含两个正整数 $a_i',b_i'$，代表 $G'$ 的一条有向线路 $(a_i',b_i')$，方向为 $a_i'\rightarrow b_i'$。

  读入完成后，你需要输出一行一个正整数 $s$，代表阶段一中神秘数字 $s$ 的值。

  在本阶段中，请注意：

  • 单个测试点内测试数据输入的先后顺序相较阶段一可能不同。
  • 对同一组测试数据，$G$ 在阶段一中无向线路定向的先后顺序与 $G'$ 在阶段二中有向线路输入的先后顺序可能不一致。
  • 两个阶段中 $G/G'$ 光团节点的编号保持不变。
  • 你必须求出当前测试数据 $G'$ 对应的神秘数字 $s$ 后才能得知下一组测试数据的信息。

交互器不是自适应的，全息光树 $G$ 的形态在交互开始前就已经确定，不会随交互流程变动。

在输出完一行后不要忘记刷新输出流。

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7
9 59
1 2
1 4
3 4
3 5
3 8
5 6
6 7
8 9

6 1
3 5
4 2
3 4
1 2
7 6

1 2
1 4
3 4
3 5
8 3
5 6
6 7
9 8

2 2
9
8 3
9 8
1 4
3 4
1 2
5 6
6 7
3 5
7
3 4
1 2
7 6
6 1
3 5
4 2

59
21

提示

样例

第一次运行时，输入如【样例 1 输入】。Neri 定向的结果如【样例 1 输出】。

注意：上述空行仅为方便理解两组测试数据之间的分隔，实际程序输出时无需打印多余的空行。

两组测试数据的所有流光线路定向后，全息光树的形态分别如下：

:::align{center}

:::

根据上述输出，第二次运行时，一种可能的输入如【样例 2 输入】，通过心灵感应，Noir 推断出阶段二的第一组数据 $s=59$，第二组数据 $s=21$。

测试工具

下发的 treedir_testing_tool.py 可以辅助你进行程序的正确性测试，并输出交互过程。测试时，将其与你编译好的程序置于同一文件夹下，然后在该文件夹的终端内运行以下命令：

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

其中：

• -q, --quiet 为可选参数，指定后测试工具不会输出交互过程。

• data_file 为你提供给测试工具的输入文件名。该文件应符合的格式如下：

  • 第一行包含两个非负整数 $T,seed$，分别代表测试数据组数与用于打乱测试数据与树内边顺序的随机数种子。如果你指定 $seed=0$，则代表不进行打乱。
  • 每组数据的格式与阶段一的输入格式相同。

• program 为你的程序名。

• arguments 为提供给你的程序的参数。

详细信息可以在测试工具的源代码内查询。

请注意：

1. 该测试工具与实际评测时的交互库实现不完全相同，评测结果不保证与实际提交时相同，仅作调试参考。
2. 测试工具只会检查你的输入是否符合格式，但不会检查你的输入是否符合数据范围（$1\le s \le 2^{n-1}$，$G$ 为一棵树等等）。
3. 测试工具不会检查你的程序是否满足时间与空间要求。