C. Yet Another Balanced Coloring Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two rooted trees with $$$n$$$ and $$$m$$$ vertices, respectively. The vertices are indexed $$$1 \ldots n$$$ (resp. $$$1 \ldots m$$$) and the root is the vertex $$$n$$$ (resp. $$$m$$$). Both trees have $$$k$$$ leaves and in both trees, the leaves are precisely the vertices with indices $$$1 \ldots k$$$. Here, the root of a tree isn't considered a leaf, even if it has only one neighbor.

For each $$$i$$$ in $$$1 \ldots k$$$, you have to choose red or blue. Then you have to paint the $$$i$$$-th vertex in both trees with the selected color.

After coloring the leaves, the following must hold in both trees:

  • For each vertex $$$u$$$, the number of red leaves in the subtree of $$$u$$$ must not differ from the number of blue leaves in the subtree of $$$u$$$ by more than one.
Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. $$$t$$$ test cases follow. Each test case is described as follows.

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n, m \le 10^5$$$).

The second line contains $$$n - 1$$$ integers $$$p_1, \ldots, p_{n - 1}$$$ ($$$i \lt p_i \le n$$$); the $$$i$$$-th of them denotes an edge between $$$i$$$ and $$$p_i$$$ in the first tree.

The third line contains $$$m - 1$$$ integers $$$q_1, \ldots, q_{m - 1}$$$ ($$$i \lt q_i \le m$$$); the $$$i$$$-th of them denotes an edge between $$$i$$$ and $$$q_i$$$ in the second tree.

It is guaranteed that in both trees, exactly the vertices $$$1 \ldots k$$$ are leaves. It is guaranteed that the sum of $$$n + m$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the answer on a separate line as follows.

  • If there is no solution, print IMPOSSIBLE.
  • Otherwise, print a string with length $$$k$$$. The $$$i$$$-th character in the string should be B if the $$$i$$$-th leaf is blue, and R otherwise.
Example
Input
2
7 7
5 5 6 6 7 7
5 6 5 6 7 7
5 4
4 4 5 5
4 4 4
Output
RBBR
RBB