T173337 未解之谜

**这是一道交互题** 珂愛是一个爱探险的女孩子。

鱼人节到了，珂愛在一个山洞里寻宝，但她迷路了。她现在想要走出去。 山洞很大，洞里有 $2^n-1$ 个洞窟和 $2^{n}-2$ 个连接洞窟的通道。你可以认为山洞是一棵满二叉树，且出口恰好在根结点的位置。 珂愛现在在某一个洞窟里，她知道的信息只有这个洞窟连接着多少条通道，并且她无法做任何标记。 由于在探宝中，珂愛消耗了大量体力，所以她现在最多移动 $150$ 次，如果 $150$ 次内没有到达出口，珂愛就只能使用禁忌的法术把山洞给炸了。 珂愛并不知道该怎么走，因此她使用魔法联系上了你，请你帮她走出山洞。 ## 任务介绍 你需要实现一个函数 `Miyafuji`，以帮助珂愛走出山洞。 - `Miyafuji(n,k)` + 树的结点个数为 $2^n-1$ + 珂愛一开始所在的洞窟有 `k` 条通道。 + 该函数结束时，你需要保证珂愛在根结点。 在每个测试点中，交互库都会调用 $T$ 次 `Miyafuji` 函数。 你可以调用函数 `Yoshika` 来告诉珂愛她的移动方式，但在单次 `Miyafuji` 函数运行时，调用 `Yoshika` 的次数不能超过 $150$。 - `Yoshika(k)` + $k$ 表示珂愛下一步走这个洞窟的第 $k$ 条通道。 + $k\geq 1$ 且不能超过这个洞窟的通道数量。 + 这个函数会返回珂愛走到的洞窟的通道数量。 在函数 `Miyafuji` 返回之后，交互库会检查状态，只有珂愛到达了根结点，才算目标完成。 保证同一个结点的通道的顺序固定，即从一个点，每次走它的第一条通道，走到的结点一定都是一样的。 ## 实现方法 **本题只支持 C++ 语言（含 C++11/C++14/C++17）**。 你需要实现的函数 `Miyafuji`： ```c++ void Miyafuji(int n,int k); ``` 函数 `Yoshika` 的接口信息如下（**你应当在程序开头加上这句话，否则会编译错误**）： ```c++ int Yoshika(int k); ```

**这是交互库的输入格式，选手不需要，也无法从标准输入中读取任何信息**。 第一行一个正整数 $T$ 表示数据组数。 对于每组数据： 第一行一个整数 $n$，表示洞窟个数为 $2^n-1$。 接下来 $2^n-2$ 行，每行两个整数 $u,v$，表示一条通道连接的两个洞窟。 接下来一行一个整数 $d$，表示珂愛一开始在的洞窟编号。

**这是交互库的输出格式，选手不需要，也无法向标准输出中写入任何信息**。 对每组数据，输出一行一个整数，表示珂愛走的步数。

对于 $100\%$ 的数据，$1\leq T\leq 100$，$1\leq n\leq 5$。 附件中提供了一个交互程序，可用来自测。实际评测时使用的交互库除了对 IO 进行了一些加密以外，没有任何不同。 附件中还提供了一个样例程序，你可以直接在其上面修改。 你可以在本地使用命令 `g++ -o code code.cpp interactive_lib.cpp` 来编译。