트리 회전

0-2 이진트리는 루트가 있는 이진트리이며, 모든 노드는 단말 노드이거나 왼쪽 자식과 오른쪽 자식을 모두 가진다.

이 문제에서는 두 트리의 모양만 비교한다. 입력에 쓰인 노드 번호는 각 트리의 구조를 설명하기 위한 번호이며, 두 트리 사이에서 같은 번호의 노드가 같은 실제 노드를 뜻하지 않는다.

허용되는 회전 위치는 두 곳이다.

• T: 현재 루트 노드에서 회전한다.
• C: 현재 루트의 오른쪽 자식 노드에서 회전한다.

각 위치에서는 왼쪽 회전 L 또는 오른쪽 회전 R을 할 수 있다. 왼쪽 회전은 회전하는 노드의 오른쪽 자식을 위로 올리고, 그 자식의 왼쪽 부분트리를 회전한 노드의 오른쪽 부분트리로 옮긴다. 오른쪽 회전은 이와 반대로 왼쪽 자식을 위로 올린다. 회전은 위로 올라올 자식이 내부 노드일 때만 0-2 이진트리를 유지한다.

두 0-2 이진트리의 회전거리는 첫 번째 트리를 두 번째 트리와 같은 모양으로 만들기 위해 필요한 허용 회전 연산의 최소 횟수이다. 두 트리가 주어졌을 때 회전거리와 그에 해당하는 연산 순서를 구하라.

첫 번째 줄에 두 트리의 노드 개수를 나타내는 정수 N이 주어진다. (5 <= N <= 300) 각 트리의 노드에는 1번부터 N번까지 번호가 붙어 있으며, 루트 노드의 번호는 항상 1이다.

다음 N개의 줄에는 첫 번째 트리의 구조가 주어진다. 각 줄에는 정수 a l r이 주어지며, l과 r은 각각 노드 a의 왼쪽 자식과 오른쪽 자식을 뜻한다. 노드 a가 단말 노드이면 l = r = 0이다. 이 N개의 줄은 a가 1부터 N까지 증가하는 순서로 주어진다.

그 다음 N개의 줄에는 두 번째 트리의 구조가 같은 형식으로 주어진다.

첫 번째 줄에 두 트리의 회전거리 M을 출력한다. 이어지는 M개의 줄에는 첫 번째 트리를 두 번째 트리와 같은 모양으로 바꾸는 회전 연산을 순서대로 출력한다.

각 회전 연산은 두 글자로 출력한다. 첫 글자는 회전 위치이며, 루트에서 회전하면 T, 루트의 오른쪽 자식에서 회전하면 C이다. 둘째 글자는 회전 방향이며, 왼쪽 회전은 L, 오른쪽 회전은 R이다. 두 글자 사이에는 공백을 넣지 않는다.

최소 횟수의 회전 순서가 여러 가지라면 그중 아무 것이나 출력한다. 허용된 회전만으로 두 트리를 같은 모양으로 만들 수 없다면 첫 번째 줄에 -1을 출력한다.