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?

-----Input-----
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.

-----Output-----
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.

-----Examples-----
Sample Input:
5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3
Sample Output:
LLRRRRLL

Difficulty: competition

Starter code:

Solutions: