나무 껴안기

옛날에 두 나무가 제자리를 잃고 서로를 향해 자라기 시작했다. 한 나무는 왼쪽에서, 다른 나무는 오른쪽에서 자랐다. 두 나무는 $n$개의 점에서 만났다.

점을 왼쪽에서 오른쪽으로 $1, 2, \ldots, n$이라 번호를 붙이면, 왼쪽 나무는 모든 점을 노드 1을 루트로 하는 하나의 부분 트리로 연결했고, 각 노드의 자식은 그 노드보다 큰 번호를 가진다. 이 부분 트리는 $n-1$개의 간선 목록으로 나타낼 수 있다.

마찬가지로 오른쪽 나무도 모든 노드를 노드 $n$을 루트로 하는 하나의 부분 트리로 연결했고, 각 노드의 자식은 그 노드보다 작은 번호를 가진다. 여기서 $n-1$개의 간선이 더 나온다.

이제 $2(n-1)$개의 간선 전체 목록이 주어졌을 때, 어떤 간선이 어느 나무에 속하는지 알아내는 것이 반드시 쉬운 것은 아니다. 이 간선들이 두 나무의 합집합이었을 수 있는지 판별하고, 가능하다면 그 배정을 구할 수 있는가?

첫째 줄에 정수 $n$이 주어진다 ($2 \le n \le 10^5$). 다음 $2(n-1)$개의 줄에는 두 정수 $u, v$가 주어지며 ($1 \le u < v \le n$), 이는 두 노드 $u$와 $v$를 잇는 간선을 나타낸다. 같은 쌍 $(u, v)$가 여러 번 연결될 수 있다.

주어진 간선들이 왼쪽에서 오른쪽으로, 또 오른쪽에서 왼쪽으로 자라는 두 나무의 합집합이 될 수 있으면, 길이 $2(n-1)$의 문자열을 출력한다. $i$번째 문자가 L이면 $i$번째 간선이 왼쪽 나무에서 온 것이고, R이면 오른쪽 나무에서 온 것이다. 그렇지 않으면 한 줄에 "impossible"을 출력한다. 답이 여러 개면 아무거나 하나 출력해도 된다.

첫 번째 예제에는 LLRRRRLL과 LLRLRRLR 두 가지 답이 있다.

두 번째 예제에는 답이 없다. LRLR은 오른쪽 나무가 거꾸로, 즉 왼쪽에서 오른쪽으로 자라는 것을 뜻하므로 올바르지 않다.