Hogwarts

Hogwarts의 새 학기가 막 시작되었지만, 무언가가 제대로 되지 않았다. 계단들이 학교 관리자들의 뜻대로 움직이지 않는다! Hogwarts에는 $N$개의 층을 연결하는 움직이는 계단이 있는 방이 하나 있다. 계단은 총 $M$개이며, 어떤 두 계단도 같은 층의 쌍을 연결하지 않는다(그리고 당연히 계단이 같은 층을 양 끝으로 연결하지도 않는다. 이들은 품위 있는 영리한 마법 계단이기 때문이다). 계단을 조작하는 유일한 방법은 각 층에 있는 빨간색 버튼과 초록색 버튼을 누르는 것이다. 각 층에는 어떤 방식으로든 $0$부터 $N-1$까지의 정수가 붙어 있다. $i$층에서 빨간색 버튼을 누르면($0\leq i \leq N-1$) 계단에 다음과 같은 변화가 일어난다. 현재 $i$층에 연결되어 있지 않은 모든 계단은 움직이지 않는다. 어떤 계단이 $i$층과 $j$층을 연결한다고 하자($j \neq i$). $i$층에서 빨간색 버튼을 누르면, 이 계단은 대신 $i$층과 $j+1 \bmod N$층을 연결한다. 단, $j+1\bmod N = i$인 경우에는 대신 $i$층과 $j+2 \bmod N =i+1 \bmod N$층을 연결한다. 초록색 버튼을 누르는 것은 같은 층에서 빨간색 버튼을 누르는 연산의 역연산이다(동등하게는 빨간색 버튼을 $N-2$번 누르는 것과 같다).

계단들만 남아 있는 동안 계단의 배치가 완전히 엉망이 되었다. 학교 관리자들은 계단을 어떻게 배치하고 싶은지에 대한 계획을 제시했다.

낮은 계급의 집요정인 당신에게 이를 바로잡는 임무가 주어졌다.

과제

계단 방을 현재 상태에서 원하는 상태로 바꾸는, 최대 $250\,000$번의 버튼 누르기로 이루어진 임의의 수열을 찾는다.

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

이어서 정수 쌍 $i$, $j$가 주어지는 $M$개의 줄이 나오며($0 \leq i,j\leq N-1$), 계단 방의 현재 상태를 나타낸다. 각 줄은 $i$층과 $j$층을 연결하는 계단이 있다는 뜻이다. 그 뒤에는 정수 쌍 $i$, $j$가 주어지는 $M$개의 줄이 더 나오며, 계단 방의 원하는 상태를 나타낸다.

출력의 첫째 줄에 버튼을 누르는 수열의 길이인 정수 하나 $Q$을 출력한다($0 \le Q \le 250\,000$). 그다음 $Q$개의 줄을 출력하며, 각 줄에는 어떤 $i$에 대해 R $i$`'' 또는 G $i$`'' 중 하나를 출력한다($0 \leq i \leq N-1$). 이는 $i$층의 빨간색 버튼 또는 초록색 버튼을 눌러야 한다는 뜻이다.