KTH Challenge 2018

#### Start

2018-04-08 08:00 UTC

## KTH Challenge 2018

#### End

2018-04-08 12:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -287 days 6:05:00

4:00:00

0:00:00

# Problem HTree Hugging

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.

Sample Input 1 Sample Output 1
5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3

LLRRRRLL

Sample Input 2 Sample Output 2
3
1 2
1 2
1 3
1 3

impossible