시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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, . . . , 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 ≤ n ≤ 105). The next 2(n−1) lines each contain two integers u, v (1 ≤ u < v ≤ 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.

예제 입력 1

5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3

예제 출력 1

LLRRRRLL

예제 입력 2

3
1 2
1 2
1 3
1 3

예제 출력 2

impossible

힌트

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.