Aitana 和 Bruno 正在玻利维亚的一个国家公园游玩。公园内有 $N$ 个地点，以及 $N-1$ 条连接两个地点的道路。通过这些道路，可以从任意地点到达任意其他地点。

在公园游玩时，他们走散了。从现在起，他们必须通过在同一时间到达同一个地点来重新会合。然而，由于身处亚马逊雨林深处，他们无法进行交流。他们唯一能依赖的是各自的地图，地图上描绘了国家公园的道路结构。他们每个人都在自己的地图上为每个地点标注了 $0, 1, \dots, N-1$ 的标签。然而，Aitana 和 Bruno 的标注方式可能不同。

Aitana 和 Bruno 现在开始移动以重新会合。在每一回合中，他们同时执行以下任一操作：移动到当前地点通过道路直接相连的地点，或者停留在当前地点。

请编写一个程序，实现一种让 Aitana 和 Bruno 重新会合的策略。在本题中，如果他们能在 $6d$ 回合内重新会合（其中 $d$ 是从 Aitana 当前所在地点到 Bruno 当前所在地点所需经过的最少道路数），则该提交可获得满分。注意，当他们在道路中间相遇时，并不被视为重新会合。

在本题中，程序需要一次性解决 $Q$ 个场景。

题目描述

在本节中，我们对问题进行形式化说明。国家公园的每个地点都被分配了一个 $0$ 到 $N-1$ 之间的 ID，第 $j$ 条道路 ($0 \le j \le N-2$) 连接 ID 为 $u_j$ 和 $v_j$ 的地点。对于 ID 为 $i$ ($0 \le i \le N-1$) 的地点，Aitana 的地图上标注的标签为 $p_i$，Bruno 的地图上标注的标签为 $q_i$。其中，$(p_0, p_1, \dots, p_{N-1})$ 和 $(q_0, q_1, \dots, q_{N-1})$ 分别是 $(0, 1, \dots, N-1)$ 的排列。

Aitana 知道，对于每个 $j = 0, 1, \dots, N-2$，存在一条连接标签为 $A_j$ 和 $B_j$ 的地点的道路，且 Aitana 目前位于标签为 $S$ 的地点。此处的“标签”基于 Aitana 的地图。因此，第 $j$ 条道路 ($0 \le j \le N-2$) 连接标签为 $p_{u_j}$ 和 $p_{v_j}$ 的地点，且 $S = p_s$，其中 $s$ 是 Aitana 当前所在地点的 ID。然而，道路给出的顺序可能不固定，且每条道路连接的两个地点在 $u_j, v_j$ 中的顺序也可能不固定。同样，Bruno 知道，对于每个 $j = 0, 1, \dots, N-2$，存在一条连接标签为 $C_j$ 和 $D_j$ 的道路，且 Bruno 目前位于标签为 $T$ 的地点。此处的“标签”基于 Bruno 的地图。特别地，$T = q_t$，其中 $t$ 是 Bruno 当前所在地点的 ID。

基于上述信息，Aitana 和 Bruno 决定接下来 $10N$ 回合的移动。换句话说，Aitana 独立决定标签序列 $x_0, x_1, \dots, x_{10N}$，Bruno 独立决定标签序列 $y_0, y_1, \dots, y_{10N}$，分别代表他们各自的移动。他们必须满足以下条件：

• $x_0 = S$，且对于每个 $k$ ($1 \le k \le 10N$)，Aitana 地图中标签为 $x_{k-1}$ 和 $x_k$ 的地点要么是同一个地点，要么通过道路直接相连。
• $y_0 = T$，且对于每个 $k$ ($1 \le k \le 10N$)，Bruno 地图中标签为 $y_{k-1}$ 和 $y_k$ 的地点要么是同一个地点，要么通过道路直接相连。

Aitana 和 Bruno 重新会合的回合数 $k^*$ 是满足标签 $x_k$（在 Aitana 的地图中）和标签 $y_k$（在 Bruno 的地图中）代表同一个地点的最小 $k$。如果 $k^* \le 6d$，则提交可获得满分。

实现细节

你必须提交一个文件 telepathy.cpp。它应实现以下函数。程序应使用预处理指令 #include 包含 telepathy.h。

• vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask) 该函数实现 Aitana 的策略。对于每个场景，该函数会被调用且仅被调用一次，总计 $Q$ 次。

  • 参数 $N$ 是国家公园的地点数。
  • 参数 $A$ 和 $B$ 是长度为 $N-1$ 的数组，对于每个 $j$ ($0 \le j \le N-2$)，$A[j]$ 和 $B[j]$ 是道路连接的两个地点的标签 $A_j$ 和 $B_j$。
  • 参数 $S$ 是 Aitana 当前所在地点的标签。
  • 参数 $subtask$ 是测试用例的子任务编号，为 $1, 2, 3$ 中的任意一个。
  • 返回值是数组 $[x_0, x_1, \dots, x_{10N}]$，代表 Aitana 的移动。
  • 返回数组的长度必须恰好为 $10N + 1$。否则，程序将被判为 Wrong Answer [1]。
  • 对于每个 $k$ ($0 \le k \le 10N$)，必须满足 $0 \le x_k \le N-1$。否则，程序将被判为 Wrong Answer [2]。
  • 必须满足 $x_0 = S$。否则，程序将被判为 Wrong Answer [3]。
  • 对于每个 $k$ ($1 \le k \le 10N$)，标签为 $x_{k-1}$ 和 $x_k$ 的地点必须是同一个地点或通过道路直接相连。否则，程序将被判为 Wrong Answer [4]。 注意，上述说明中的“标签”基于 Aitana 的标注。

• vector<int> Bruno(int N, vector<int> C, vector<int> D, int T, int subtask) 该函数实现 Bruno 的策略。对于每个场景，该函数在 Aitana 函数调用后被调用且仅被调用一次，总计 $Q$ 次。

  • 参数 $N$ 是国家公园的地点数。
  • 参数 $C$ 和 $D$ 是长度为 $N-1$ 的数组，对于每个 $j$ ($0 \le j \le N-2$)，$C[j]$ 和 $D[j]$ 是道路连接的两个地点的标签 $C_j$ 和 $D_j$。
  • 参数 $T$ 是 Bruno 当前所在地点的标签。
  • 参数 $subtask$ 是测试用例的子任务编号，为 $1, 2, 3$ 中的任意一个。
  • 返回值是数组 $[y_0, y_1, \dots, y_{10N}]$，代表 Bruno 的移动。
  • 返回数组的长度必须恰好为 $10N + 1$。否则，程序将被判为 Wrong Answer [5]。
  • 对于每个 $k$ ($0 \le k \le 10N$)，必须满足 $0 \le y_k \le N-1$。否则，程序将被判为 Wrong Answer [6]。
  • 必须满足 $y_0 = T$。否则，程序将被判为 Wrong Answer [7]。
  • 对于每个 $k$ ($1 \le k \le 10N$)，标签为 $y_{k-1}$ 和 $y_k$ 的地点必须是同一个地点或通过道路直接相连。否则，程序将被判为 Wrong Answer [8]。 注意，上述说明中的“标签”基于 Bruno 的标注。

如果 Aitana 和 Bruno 在 $10N$ 回合内没有会合，即对于每个 $k$ ($0 \le k \le 10N$)，Aitana 地图中标签为 $x_k$ 的地点和 Bruno 地图中标签为 $y_k$ 的地点不同，程序将被判为 Wrong Answer [9]。

重要提示

• 你的程序可以实现其他内部函数或使用全局变量。在评测时，它将作为 Aitana 和 Bruno 的两个进程执行，因此 Aitana 的进程和 Bruno 的进程无法共享全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

样例

国家公园的道路结构、Aitana 的地图和 Bruno 的地图

在此示例中，Aitana 的移动方式使得她在每一回合分别位于标签为 $1, 0, 0, 1, 2, \dots, 2$ 的地点（在她的地图中）。Bruno 的移动方式使得他在每一回合分别位于标签为 $2, 2, 0, 0, 1, \dots, 1$ 的地点（在他的地图中）。他们在第 3 回合结束时重新会合。此时，Aitana 位于标签为 $1$ 的地点（在她的地图中），Bruno 位于标签为 $0$ 的地点（在他的地图中），这表示同一个地点。

输入格式 1

2
Aitana(3, [0, 1], [1, 2], 1, 2)
[1, 0, 0, 1, 2, ..., 2]
Bruno(3, [1, 0], [2, 0], 2, 2)
[2, 2, 0, 0, 1, ..., 1]

输出格式 1

Case #0: Accepted 3 1
Case #1: Accepted 3 1

说明

在上述样例中，部分返回值被省略，但每个数组的长度均为 31。