你在和李晨玩一个奇怪的游戏。您有一棵树,在一张纸上绘制了 $$$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}$$$ 的值你们都知道。
图中显示了可能的树的两个标签:左边是你的,右边是李晨的。选定的树会突出显示。有两个公共节点。
您想要确定您的子树是否至少有一个公共顶点。幸运的是,你的朋友安德鲁知道这棵树的两个标签。您最多可以向 Andrew 提出 $$$5$$$ 问题,每个问题采用以下两种形式之一:
- A x:安德鲁会查看你的标签中的顶点$$$x$$$,并告诉你这个顶点在李晨的标签中的编号。
- B y:Andrew 会查看 Li Chen 标签中的顶点 $$$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$$$) — Li Chen 子树中的节点数。
下一行包含 $$$k_2$$$ 不同的整数 $$$y_1, y_2, \ldots, y_{k_2}$$$ ($$$1 \leq y_i \leq n$$$) — Li Chen 子树中节点的索引(根据 Li Chen 的标记)。根据李晨对树节点的标注,保证这些顶点形成一棵子树。
测试用例将一一提供,因此您必须完成与上一个测试的交互(即打印出公共节点,如果没有该节点则打印 $$$-1$$$)才能开始接收下一个测试。
您可以向安德鲁提出两种不同类型的问题。
- 您可以打印“A x”($$$1 \leq x \leq n$$$)。 Andrew 会查看您的标签中的顶点 $$$x$$$,并用李晨标签中该顶点的编号来回复您。
- 您可以打印“B y”($$$1 \leq y \leq n$$$)。 Andrew 会查看 Li Chen 标签中的顶点 $$$y$$$,并用您标签中该顶点的编号来回复您。
每棵树最多只能提出 $$$5$$$ 问题。
当你准备好回答时,打印“C s”,其中 $$$s$$$ 是两个子树共有的顶点的标签,或者 $$$-1$$$(如果不存在这样的顶点)。打印答案不算是问题。请记住刷新您的答案以开始接收下一个测试用例。
打印问题后,不要忘记打印行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
如果法官回答 $$$-1$$$,则意味着您提出的查询超出了允许的范围,或者提出了无效的查询。您的程序应立即终止(例如,通过调用 exit(0))。您将收到错误答案;这意味着您提出的查询超出了允许的范围,或者提出了无效的查询。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。
黑客格式
要破解,请使用以下格式。请注意,您只能使用一个测试用例进行破解。
第一行应包含单个整数 $$$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$$$)。根据上面的排列,这些顶点应该在李晨的树中形成一棵子树。
示例
输入 #1
1 3 1 2 2 3 1 1 1 2 2 1
输出 #1
A 1 B 2 C 1
输入 #2
2 6 1 2 1 3 1 4 4 5 4 6 4 1 3 4 5 3 3 5 2 3 6 1 2 1 3 1 4 4 5 4 6 3 1 2 3 3 4 1 6 5
输出 #2
B 2 C 1 A 1 C -1
注意
对于第一个样本,李晨的隐藏排列为 $$$[2, 3, 1]$$$,对于第二个样本,他的隐藏排列为 $$$[5, 3, 2, 4, 1, 6]$$$。
在第一个示例中,有一棵树,其中三个节点排成一行。上面是你如何标记树和你选择的子树,下面是李晨如何标记他选择的树和子树:
在第一个问题中,你让Andrew查看你标签中的节点$$$1$$$,并告诉你它在李晨标签中的标签。安德鲁回复$$$2$$$。此时,您知道两个子树都包含相同的节点(即根据您的标签,节点 $$$1$$$ ),因此您可以输出“C 1”并完成。不过,你也可以让Andrew看看李晨标签中的节点$$$2$$$,并告诉你它在你的标签中的标签。 Andrew 回复 $$$1$$$(执行此步骤的唯一原因是向您展示如何提问)。
对于第二个示例,有两个测试用例。第一个看起来是声明中的:
我们首先询问“B 2”,Andrew会告诉我们$$$3$$$。在这种情况下,我们知道 $$$3$$$ 是一个公共顶点,此外,任何包含节点 $$$3$$$ 且大小为 $$$3$$$ 的子树也必须包含节点 $$$1$$$,因此我们可以输出“C 1”或“C 3”作为我们的答案。
在第二个示例中的第二种情况下,情况如下所示:
在这种情况下,您知道大小为 $$$3$$$ 且不包含节点 $$$1$$$ 的唯一子树是子树 $$$4,5,6$$$。你向Andrew询问李晨标签中节点$$$1$$$的标签,Andrew说$$$5$$$。在这种情况下,您知道李晨的子树不包含节点$$$1$$$,因此他的子树必须由节点$$$4,5,6$$$(在您的标签中)组成,因此两个子树没有公共节点。