Description:
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.
Input Format:
None
Output Format:
None
Note:
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.