CF1044B.Intersecting Subtrees

You are playing a strange game with Li Chen. You have a tree with $n$ nodes drawn on a piece of paper. All nodes are unlabeled and distinguishable. Each of you independently labeled the vertices from $1$ to $n$. Neither of you know the other's labelling of the tree.

You and Li Chen each chose a subtree (i.e., a connected subgraph) in that tree. Your subtree consists of the vertices labeled $x_1, x_2, \ldots, x_{k_1}$ in your labeling, Li Chen's subtree consists of the vertices labeled $y_1, y_2, \ldots, y_{k_2}$ in his labeling. The values of $x_1, x_2, \ldots, x_{k_1}$ and $y_1, y_2, \ldots, y_{k_2}$ are known to both of you.

The picture shows two labelings of a possible tree: yours on the left and Li Chen's on the right. The selected trees are highlighted. There are two common nodes.

You want to determine whether your subtrees have at least one common vertex. Luckily, your friend Andrew knows both labelings of the tree. You can ask Andrew at most $5$ questions, each of which is in one of the following two forms:

• A x: Andrew will look at vertex $x$ in your labeling and tell you the number of this vertex in Li Chen's labeling.
• B y: Andrew will look at vertex $y$ in Li Chen's labeling and tell you the number of this vertex in your labeling.

Determine whether the two subtrees have at least one common vertex after asking some questions. If there is at least one common vertex, determine one of your labels for any of the common vertices.

Interaction

Each test consists of several test cases.

The first line of input contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

For each testcase, your program should interact in the following format.

The first line contains a single integer $n$ ($1 \leq n \leq 1\,000$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ ($1\leq a_i, b_i\leq n$) — the edges of the tree, indicating an edge between node $a_i$ and $b_i$ according to your labeling of the nodes.

The next line contains a single integer $k_1$ ($1 \leq k_1 \leq n$) — the number of nodes in your subtree.

The next line contains $k_1$ distinct integers $x_1,x_2,\ldots,x_{k_1}$ ($1 \leq x_i \leq n$) — the indices of the nodes in your subtree, according to your labeling. It is guaranteed that these vertices form a subtree.

The next line contains a single integer $k_2$ ($1 \leq k_2 \leq n$) — the number of nodes in Li Chen's subtree.

The next line contains $k_2$ distinct integers $y_1, y_2, \ldots, y_{k_2}$ ($1 \leq y_i \leq n$) — the indices (according to Li Chen's labeling) of the nodes in Li Chen's subtree. It is guaranteed that these vertices form a subtree according to Li Chen's labelling of the tree's nodes.

Test cases will be provided one by one, so you must complete interacting with the previous test (i.e. by printing out a common node or $-1$ if there is not such node) to start receiving the next one.

You can ask the Andrew two different types of questions.

• You can print "A x" ($1 \leq x \leq n$). Andrew will look at vertex $x$ in your labeling and respond to you with the number of this vertex in Li Chen's labeling.
• You can print "B y" ($1 \leq y \leq n$). Andrew will look at vertex $y$ in Li Chen's labeling and respond to you with the number of this vertex in your labeling.

You may only ask at most $5$ questions per tree.

When you are ready to answer, print "C s", where $s$ is your label of a vertex that is common to both subtrees, or $-1$, if no such vertex exists. Printing the answer does not count as a question. Remember to flush your answer to start receiving the next test case.

After printing a question do not forget to print end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

If the judge responds with $-1$, it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive Wrong Answer; it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer $t$ ($t=1$).

The second line should contain a single integer $n$ ($1 \leq n \leq 1\,000$).

The third line should contain $n$ integers $p_1, p_2, \ldots, p_n$ ($1\leq p_i\leq n$) — a permutation of $1$ to $n$. This encodes the labels that Li Chen chose for his tree. In particular, Li Chen chose label $p_i$ for the node you labeled $i$.

Each of the next $n-1$ lines should contain two integers $a_i$ and $b_i$ ($1\leq a_i, b_i\leq n$). These edges should form a tree.

The next line should contain a single integer $k_1$ ($1 \leq k_1 \leq n$).

The next line should contain $k_1$ distinct integers $x_1,x_2,\ldots,x_{k_1}$ ($1 \leq x_i \leq n$). These vertices should form a subtree.

The next line should contain a single integer $k_2$ ($1 \leq k_2 \leq n$).

The next line should contain $k_2$ distinct integers $y_1, y_2, \ldots, y_{k_2}$ ($1 \leq y_i \leq n$). These vertices should form a subtree in Li Chen's tree according to the permutation above.

你正在和李晨玩一个奇怪的游戏。你有一棵画在纸上的、包含 $n$ 个节点的树。所有节点均无标签，但彼此可区分。你们各自独立地将这棵树的顶点从 $1$ 到 $n$ 编号。双方都不知道对方对树的编号方式。

你和李晨各自在这棵树中选择了一个子树（即一个连通子图）。你的子树由你在自己的编号下标记为 $x_1, x_2, \ldots, x_{k_1}$ 的顶点构成；李晨的子树由他在自己的编号下标记为 $y_1, y_2, \ldots, y_{k_2}$ 的顶点构成。$x_1, x_2, \ldots, x_{k_1}$ 和 $y_1, y_2, \ldots, y_{k_2}$ 的具体取值双方均已知。

图中展示了同一棵树的两种可能编号方式：左侧是你的编号，右侧是李晨的编号。被选中的子树已高亮标出。其中共有两个公共顶点。

你想判断你们的子树是否至少有一个公共顶点。幸运的是，你的朋友安德鲁同时知道这两种编号方式。你可以向安德鲁最多提问 $5$ 次，每次提问必须是以下两种形式之一：

• A x：安德鲁查看你在编号中为 $x$ 的顶点，并告诉你该顶点在李晨编号中对应的数字；
• B y：安德鲁查看李晨编号中为 $y$ 的顶点，并告诉你该顶点在你的编号中对应的数字。

在提出若干问题后，请判断两个子树是否至少有一个公共顶点；若存在，则输出任意一个公共顶点在你编号下的标签。

交互方式

每个测试包含若干测试用例。

输入的第一行是一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

对于每个测试用例，你的程序需按如下格式进行交互：

第一行是一个整数 $n$（$1 \leq n \leq 1\,000$），表示树中节点的数量。

接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$），表示树的一条边，该边连接你在编号中为 $a_i$ 和 $b_i$ 的两个节点。

下一行是一个整数 $k_1$（$1 \leq k_1 \leq n$），表示你所选子树中节点的数量。

再下一行包含 $k_1$ 个互不相同的整数 $x_1, x_2, \ldots, x_{k_1}$（$1 \leq x_i \leq n$），表示你在编号中选出的子树的节点索引。保证这些顶点构成一棵子树。

再下一行是一个整数 $k_2$（$1 \leq k_2 \leq n$），表示李晨所选子树中节点的数量。

再下一行包含 $k_2$ 个互不相同的整数 $y_1, y_2, \ldots, y_{k_2}$（$1 \leq y_i \leq n$），表示李晨编号中选出的子树的节点索引。保证这些顶点按李晨的编号方式构成一棵子树。

测试用例将逐个提供，因此你必须完成与前一个测试用例的交互（即输出一个公共顶点的你的编号，或输出 $-1$ 表示不存在公共顶点），才能开始接收下一个测试用例。

你可以向安德鲁提出两种类型的问题：

• 你可以输出 "A x"（$1 \leq x \leq n$）：安德鲁查看你在编号中为 $x$ 的顶点，并回复该顶点在李晨编号中对应的数字；
• 你可以输出 "B y"（$1 \leq y \leq n$）：安德鲁查看李晨编号中为 $y$ 的顶点，并回复该顶点在你的编号中对应的数字。

每棵树至多允许提出 $5$ 个问题。

当你准备作答时，请输出 "C s"，其中 $s$ 是一个同时属于两个子树的顶点在你编号下的标签；若不存在这样的顶点，则 $s = -1$。输出答案不计入提问次数。请务必刷新输出，以开始接收下一个测试用例。

每次输出提问后，请勿忘记输出换行符并刷新输出。否则你会收到“空闲超限”（Idleness limit exceeded）错误。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• 其他语言请参阅相应文档。

如果评测系统返回 $-1$，说明你提问次数超过限制，或提问格式非法。此时你的程序应立即终止（例如调用 exit(0)）。你将获得“答案错误”（Wrong Answer）判决；这意味着你提问次数超限或提问非法。若忽略此情况，你的程序将继续从已关闭的流中读取数据，从而可能导致其他错误判决。

Hack 格式

用于 hack 时，请采用以下格式。注意：你只能用单个测试用例进行 hack。

第一行应为一个整数 $t$（$t = 1$）。

第二行应为一个整数 $n$（$1 \leq n \leq 1\,000$）。

第三行应为 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示 $1$ 到 $n$ 的一个排列。它编码了李晨为其树所选择的编号：具体而言，李晨把你编号为 $i$ 的节点编号为 $p_i$。

接下来 $n-1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$），这些边应构成一棵树。

下一行应为一个整数 $k_1$（$1 \leq k_1 \leq n$）。

再下一行应为 $k_1$ 个互不相同的整数 $x_1, x_2, \ldots, x_{k_1}$（$1 \leq x_i \leq n$），这些顶点应构成一棵子树。

再下一行应为一个整数 $k_2$（$1 \leq k_2 \leq n$）。

再下一行应为 $k_2$ 个互不相同的整数 $y_1, y_2, \ldots, y_{k_2}$（$1 \leq y_i \leq n$），这些顶点应按上述排列方式，在李晨的树中构成一棵子树。

For the first sample, Li Chen's hidden permutation is $[2, 3, 1]$, and for the second, his hidden permutation is $[5, 3, 2, 4, 1, 6]$ for both cases.

In the first sample, there is a tree with three nodes in a line. On the top, is how you labeled the tree and the subtree you chose, and the bottom is how Li Chen labeled the tree and the subtree he chose:

In the first question, you ask Andrew to look at node $1$ in your labelling and tell you the label of it in Li Chen's labelling. Andrew responds with $2$. At this point, you know that both of your subtrees contain the same node (i.e. node $1$ according to your labeling), so you can output "C 1" and finish. However, you can also ask Andrew to look at node $2$ in Li Chen's labelling and tell you the label of it in your labelling. Andrew responds with $1$ (this step was given with the only reason — to show you how to ask questions).

For the second sample, there are two test cases. The first looks is the one from the statement:

We first ask "B 2", and Andrew will tell us $3$. In this case, we know $3$ is a common vertex, and moreover, any subtree with size $3$ that contains node $3$ must contain node $1$ as well, so we can output either "C 1" or "C 3" as our answer.

In the second case in the second sample, the situation looks as follows:

In this case, you know that the only subtree of size $3$ that doesn't contain node $1$ is subtree $4,5,6$. You ask Andrew for the label of node $1$ in Li Chen's labelling and Andrew says $5$. In this case, you know that Li Chen's subtree doesn't contain node $1$, so his subtree must be consist of the nodes $4,5,6$ (in your labelling), thus the two subtrees have no common nodes.

对于第一个样例，李晨的隐藏排列为 $[2, 3, 1]$；对于第二个样例，两个测试用例中李晨的隐藏排列均为 $[5, 3, 2, 4, 1, 6]$。

在第一个样例中，存在一棵三个节点呈链状的树。上方图示为你对这棵树的标号方式以及你所选择的子树，下方图示为李晨对该树的标号方式以及他所选择的子树：

在第一个问题中，你请安德鲁查看你标号下的节点 $1$，并告诉你该节点在李晨标号下的对应标签。安德鲁回答为 $2$。此时，你已知你们两人所选的子树均包含同一个节点（即按你的标号为节点 $1$），因此你可以输出 "C 1" 并结束交互。当然，你也可以改为询问安德鲁：在李晨的标号下，节点 $2$ 对应你标号下的哪个节点？安德鲁将回答 $1$（此步仅用于向你演示如何提问）。

在第二个样例中，共有两个测试用例。第一个测试用例即题目陈述中所给的情形：

我们首先提问 "B 2"，安德鲁将回答 $3$。此时，我们得知 $3$ 是一个公共顶点；进一步地，任何大小为 $3$ 且包含节点 $3$ 的子树也必然包含节点 $1$，因此我们可以输出 "C 1" 或 "C 3" 作为答案。

第二个样例中的第二个测试用例情形如下：

在此情形下，你知道：唯一一个大小为 $3$ 且不包含节点 $1$ 的子树是 $\{4,5,6\}$。于是你向安德鲁询问节点 $1$ 在李晨标号下的对应标签，安德鲁回答为 $5$。此时，你便知道李晨所选的子树不包含节点 $1$，因此他的子树必定由节点 $4,5,6$（按你的标号）构成，故两棵子树无公共节点。