Hide

Problem T
Hogwarts

The new semester at Hogwarts has just started, but something is not quite right – 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, and no two staircases connect the same pair of floors (and, obviously, a staircase would not connect a floor to itself – these are smart magic staircases with dignity). The only way to manipulate the staircases is by pressing red and green buttons located on each floor. The floors are labeled in some manner by the integers $0$ through $N-1$. Pressing the red button on floor $i$ ($0\leq i \leq N-1$) has the following effect on the staircases. Any staircase that is currently not connected to floor $i$ does not move. Suppose a staircase connects floors $i$ and $j$ ($j \neq i$). After pressing the red button on floor $i$, it will instead connect floors $i$ and $j+1 \bmod N$ – unless $j+1\bmod N = i$, in which case it will connect floors $i$ and $j+2 \bmod N =i+1 \bmod N$ instead. Pressing the green button is simply the inverse operation of pressing the red one on the same floor (or, equivalently, the same as pressing the red one $N-2$ times).

While alone, the staircases got all messed up. The school adminstrators have presented a plan for how they would rather like the staircases to be placed.

You, a low-ranking house elf, have been given the task to fix this.

Task

Find some sequence of at most $250\, 000$ button presses that will change the staircase room from its current state to the desired state.

Input

There is a single test case. On the first line $N$ and $M$ are given ($3 \leq N \leq 50$, $0 \leq M \leq N(N-1)/2$).

Then follow $M$ lines with pairs of integers $i$, $j$ ($0 \leq i,j\leq N-1$), describing the current state of the room of staircases. Each such line means that there is a staircase connecting floors $i$ and $j$. After this follow another $M$ lines with pairs of integers $i$, $j$, describing the desired state of the room of staircases.

You may assume that neither the current state of the room nor the desired state of the room contains two staircases between the same pairs of floors (but some pairs of floors may appear in both the current and desired states of the room).

Output

On the first line of output, write a single integer $Q$ ($0 \le Q \le 250\, 000$), the length of your sequence of button presses. Then print $Q$ lines, each being either “R $i$” or “G $i$” for some $i$ ($0 \leq i \leq N-1$), meaning that the red or green button on floor $i$ should be pressed.

Sample Input 1 Sample Output 1
5 4
0 1
0 3
1 2
2 4
0 2
0 4
2 3
2 4
2
R 0
G 2
Sample Input 2 Sample Output 2
3 3
0 1
0 2
1 2
0 1
1 2
0 2
0

Please log in to submit a solution to this problem

Log in