호그와트 계단

호그와트의 새 학기가 시작되었지만 계단이 관리자의 뜻대로 움직이지 않는다. 호그와트에는 $N$개 층을 잇는 움직이는 계단이 한 방에 모여 있다. 계단은 모두 $M$개이다. 같은 두 층을 잇는 계단은 둘 이상 없고, 계단은 한 층을 그 자신과 잇지 않는다.

계단을 조작하는 방법은 각 층에 있는 빨간 단추와 초록 단추를 누르는 것뿐이다. 층에는 $0$부터 $N-1$까지의 번호가 붙어 있다.

층 $i$ ($0 \le i \le N-1$)의 빨간 단추를 누르면 다음이 일어난다. 지금 층 $i$와 연결되어 있지 않은 계단은 그대로 둔다. 층 $i$와 층 $j$ ($j \neq i$)를 잇는 계단은, 누른 뒤에 층 $i$와 층 $j+1 \bmod N$을 잇는다. 다만 $j+1 \bmod N = i$이면 층 $i$와 층 $j+2 \bmod N$을 잇고, 이는 $i+1 \bmod N$과 같다.

초록 단추를 누르는 것은 같은 층의 빨간 단추를 누르는 연산의 역연산이다. 같은 층의 빨간 단추를 $N-2$번 누르는 것과 같다.

혼자 남은 계단이 뒤섞였다. 관리자는 원하는 배치를 제시했다. 낮은 직급의 집요정인 당신은 현재 배치를 그 원하는 배치로 바꿔야 한다.

단추를 눌러 현재 배치를 목표 배치로 바꾸는 수열 가운데 길이가 가장 짧은 것을 출력한다. 최단 수열이 여러 개이면 사전 순으로 가장 앞선 것을 출력한다. 수열의 각 항은 문자열 R i 또는 G i이고, 비교할 때 문자 R이 G보다 앞이며 층 번호가 작은 쪽이 앞이다.

테스트 케이스는 하나이다. 첫 줄에 $N$과 $M$이 주어진다 ($3 \le N \le 50$, $0 \le M \le N(N-1)/2$).

다음 $M$줄에 정수 쌍 $i$, $j$ ($0 \le i, j \le N-1$)가 주어진다. 각 줄은 현재 상태에서 층 $i$와 층 $j$를 잇는 계단을 뜻한다. 그다음 $M$줄에 정수 쌍 $i$, $j$가 주어지고, 목표 상태에서 층 $i$와 층 $j$를 잇는 계단을 뜻한다.

현재 상태와 목표 상태 모두 같은 두 층 사이에 계단을 두 개 이상 두지 않는다. 어떤 두 층 쌍은 현재 상태와 목표 상태에 함께 나타날 수 있다. 현재 상태에서 목표 상태로 가는 수열이 항상 존재한다.

첫 줄에 수열의 길이 $Q$를 출력한다 ($0 \le Q \le 250000$). 이어지는 $Q$줄 각각에 R i 또는 G i를 출력한다. $i$는 $0 \le i \le N-1$인 층 번호이다. R i는 층 $i$의 빨간 단추를, G i는 층 $i$의 초록 단추를 누름을 뜻한다.

출력하는 수열은 위에서 정한 최단, 사전 순 기준을 만족하는 유일한 수열이어야 한다.