Once, two trees forgot their place and started to grow into each other. One of the trees grew from the left, and the other from the right. On $n$ points, they collided.
Numbering the points $1, 2, \dots , n$ from left to right, the left tree ended up connecting all of them in a single subtree rooted in node $1$, such that every node’s children had larger numbers than the node itself. We can describe this subtree with a list of $n-1$ edges.
Similarly, the right tree also connected all nodes in a single subtree rooted in node $n$, with every node’s children having smaller numbers than the node itself. This yields an additional $n-1$ edges.
Now, given the full list of $2(n-1)$ edges, it is not necessarily easy to tell which edge belongs to which tree. Can you figure out a possible assignment, or determine that it is impossible for this collection to have been the union of two trees?
The first line of input contains the integer $n$ ($2 \le n \le 10^5$). The next $2(n-1)$ lines each contain two integers $u, v$ ($1 \le u < v \le n$) indicating an edge joining the two nodes $u$ and $v$. A pair $(u, v)$ may be connected by more than one edge.
If it is possible for the edges to be the union of two trees that grow left-to-right and right-to-left, output a string of length $2(n-1)$, where the $i$’s character is L if the $i$’th edge should come from the left tree, or R if it should come from the right tree. Otherwise, output the word “impossible” on a single line. If there are multiple solutions, you may output any one of them.
Explanation of Sample Inputs
In the first example, there are two solutions: LLRRRRLL and LLRLRRLR.
In the second example, there are no solutions. Note that LRLR is not valid, because it would involve the right tree growing backward, from left to right.
|Sample Input 1||Sample Output 1|
5 1 2 2 5 2 3 1 3 3 5 4 5 3 4 1 3
|Sample Input 2||Sample Output 2|
3 1 2 1 2 1 3 1 3