Hogwarts staircases

The new semester at Hogwarts has just started, but the staircases are not cooperating with the school administrators. Hogwarts has a single room of movable staircases connecting the $N$ floors. There are $M$ staircases in total. No two staircases connect the same pair of floors, and a staircase does not connect a floor to itself.

The only way to manipulate the staircases is by pressing red and green buttons on each floor. The floors are labeled $0$ to $N-1$.

Pressing the red button on floor $i$ ($0 \le i \le N-1$) has the following effect. Any staircase that is not currently connected to floor $i$ does not move. If a staircase connects floors $i$ and $j$ ($j \neq i$), it then connects floors $i$ and $j+1 \bmod N$, unless $j+1 \bmod N = i$, in which case it connects floors $i$ and $j+2 \bmod N$, which equals $i+1 \bmod N$.

Pressing the green button is the inverse of pressing the red button on the same floor. Equivalently, it is the same as pressing the red button $N-2$ times.

While left alone, the staircases became jumbled. The administrators have a desired placement. You are a low-ranking house elf, and you must realize that plan.

Print a shortest sequence of button presses that changes the current layout into the desired layout. If several shortest sequences exist, print the lexicographically smallest one. Each press is the string R i or G i. The letter R comes before G, and a smaller floor index comes before a larger one.

There is a single test case. The first line contains $N$ and $M$ ($3 \le N \le 50$, $0 \le M \le N(N-1)/2$).

Then follow $M$ lines of integers $i$, $j$ ($0 \le i, j \le N-1$), the current staircases. Each line means a staircase connects floors $i$ and $j$. Then follow another $M$ lines of integers $i$, $j$, the desired staircases.

Neither layout contains two staircases between the same pair of floors. Some pairs may appear in both layouts. A sequence from the current layout to the desired layout always exists.

On the first line print a single integer $Q$ ($0 \le Q \le 250000$), the length of the sequence. Then print $Q$ lines, each R i or G i for some $i$ ($0 \le i \le N-1$), meaning the red or green button on floor $i$ is pressed.

The sequence must be the unique shortest sequence under the lexicographic rule above.