Tree Rotation

A 0-2 binary tree is a rooted binary tree in which every node is either a leaf or has both a left child and a right child.

Only the shape of each tree matters in this problem. The node numbers in the input identify nodes inside one tree description; the same number in the two descriptions does not mean the same physical node.

A rotation may be applied at one of two positions.

• T: rotate at the current root.
• C: rotate at the current root's right child.

At either position, a left rotation L or a right rotation R may be used. A left rotation moves the rotated node's right child upward and moves that child's left subtree to become the rotated node's right subtree. A right rotation is the symmetric operation. A rotation preserves a 0-2 binary tree only when the child being moved upward is an internal node.

The rotation distance between two 0-2 binary trees is the minimum number of allowed rotations needed to change the first tree into the same shape as the second tree. Given two trees, output this distance and one corresponding sequence of rotations.

The first line contains an integer N, the number of nodes in each tree. (5 <= N <= 300) In each tree, nodes are numbered from 1 to N, and node 1 is always the root.

The next N lines describe the first tree. Each line contains three integers a l r, meaning that l and r are respectively the left and right children of node a. If node a is a leaf, then l = r = 0. These N lines are given in increasing order of a from 1 to N.

The following N lines describe the second tree in the same format.

Print the rotation distance M on the first line. Then print M lines, in order, describing rotations that transform the first tree into the same shape as the second tree.

Each rotation is written as two characters. The first character is the position: T for the root, or C for the root's right child. The second character is the direction: L for a left rotation, or R for a right rotation. Do not print a space between the two characters.

If several shortest rotation sequences exist, print any one of them. If the two trees cannot be made equal in shape using the allowed rotations, print -1 on the first line.