给定一棵$n$个节点的无向树，以及神秘数字$s$（$1 \le s \le 2^{n-1}$）。

1. 阶段1：程序会依次收到树的$n-1$条无向边，每收到一条边必须立刻为其指定方向，最终形成一棵有向树。
2. 阶段2：程序会收到阶段1生成的完整有向树，需要根据有向树结构，准确还原出神秘数字$s$。

要求：保证对任意合法的$n,s$、任意树结构、任意边输入顺序，都能正确完成信息传递。 数据范围：$1 \le T \le 10^4$，$3 \le n \le 30$。

本题的数据范围已经说明了做法，剩下的就是细节问题了：

首先将 $s$ 减1得到 $s'$，把范围从 $[1,2^{n-1}]$ 转化为 $[0,2^{n-1}-1]$，恰好对应一个 $n-1$ 位的二进制数。

首先很明显就是通过编号 $i$ 来存储第 $i-1$ 二进制位的情况，然后我们发现好像还会剩余一个点，此外剩下的问题就是如何通过对于边的定向来解决位数和顺序。

一般这种二进制的题目都是通过异或来完成操作。

不难想到，我们可以考虑类似于钦定编号 $n$ 的具体权值，然后通过相邻边来推出其余点的权值。

考虑下面的方式进行定向:

定义编号 $b_i = (s' >> (i-1)) \& 1$

对于任意一条无向边$(u,v)$，定向仅由两个端点的标记决定，例如下面的规则：

• 若$b_u = b_v$，定向为小编号→大编号（$u\to v$，当 u<v 时）；
• 若$b_u \neq b_v$，定向为大编号→小编号（$v\to u$，当 u<v 时）。

然后通过下面方法进行恢复:

• 对于原无向边$(u,v)$（u<v），若最终定向为$u\to v$，说明 $b_u = b_v$，即 $b_u \oplus b_v = 0$；
• 若定向为$v\to u$，说明$b_u \neq b_v$，即$b_u \oplus b_v = 1$。

基于所有相邻节点的异或关系，固定根节点 $b_{n}=0$，通过DFS/BFS遍历整棵树，即可推出所有节点的 $b_i$ ，拼接得到 $s'$，加1后即为原数字 $s$。