30401번 - 목걸이 만들기

문제

교내의 많은 커플들 탓에 옆구리가 시렸던 창현이는 평소 좋아했던 민준이에게 고백하기로 마음먹었다.

창현이는 민준이가 물질적인 선물을 좋아한다는 것을 알고 있기 때문에 목걸이를 만들어 고백할 때 선물로 주기로 했다. 창현이는 $ N $개의 실과 $N$개의 구슬로 이루어진 목걸이를 가지고 있다. 또, 창현이의 목걸이는 구슬에 적당히 1ドル$부터 $N$까지의 번호를 붙였을 때 1ドル \le i,j \le N$이고 $i \equiv j \pm 1 \pmod{N}$인 정수 $i,ドル $j$에 대해 $i$번 구슬과 $j$번 구슬은 반드시 하나의 실로 연결되어 있음이 보장된다. 민준이는 화려한 선물을 좋아하기 때문에 창현이는 $M$개의 실과 $M$개의 구슬을 이용해 목걸이를 꾸미기로 했다.

먼저, 창현이는 30개보다 적은 수의 구슬들을 실로 연결하여 $N$개 이하의 장식을 만든다. 창현이는 장식을 만들 때 구슬의 수를 실의 수보다 하나 더 많게 만든다. 장식을 만든 다음 창현이는 장식을 이루는 구슬 중 하나와 원래 목걸이의 구슬 중 하나를 한 개의 실에 연결한다. 창현이는 이 과정을 반복하여 모든 장식을 원래 목걸이에 연결하며, 이때 창현이는 두 개 이상의 장식을 같은 구슬에 연결하지 않고, 장식을 달기 전의 목걸이를 이루는 구슬이 아닌 구슬에 장식을 달지 않는다.

드디어 고백하기로 한 날이 다가왔고 창현이는 목걸이를 가지고 민준이에게 찾아갔다. 하지만, 창현이는 큰 문제를 깨달았다. 민준이가 창현이가 만든 목걸이와 같은 목걸이를 끼고 있었던 것이다. 창현이는 바로 목걸이를 다시 만들기로 했다.

창현이는 새로 만든 목걸이와 전에 만든 목걸이가 같은 목걸이인지 확인하려고 한다. 두 목걸이가 주어졌을 때, 두 목걸이가 같은 것인지 판단하는 프로그램을 작성하라.

두 목걸이가 같다는 것은 아래와 같이 정의한다.

꾸며진 두 목걸이 $A,ドル $B$ 가 있다고 하자. $A$와 $B$ 의 구슬에 적당히 번호를 붙였을 때 임의의 두 번호 $ 1 \le x, y \le N+M ,ドル $ x \neq y$에 대해서 $A$에서 $x$번, $y$번 구슬이 하나의 실로 연결되는 것과 $B$에서 $x$번, $y$번 구슬이 하나의 실로 연결되는 것이 필요충분조건이면 목걸이 $A$와 $B$가 같다고 정의한다.

입력

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N+M$개의 줄에 걸쳐 $u_i , v_i$가 차례대로 주어지고, 이는 이전에 만들었던 목걸이를 이루는 구슬 $u_i$와 구슬 $v_i$가 실로 연결되어 있다는 것을 의미한다.

$N+M+2$번째 줄부터, $N+M$개의 줄에 거쳐 $x_j , y_j$가 차례대로 주어진다. 이는 새로 만든 목걸이를 이루는 구슬 $x_j$와 $y_j$가 실로 연결되어 있다는 것을 의미한다.

출력

두 목걸이가 다르다면 Go to Minjun을, 같다면 Retry를 출력하라

제한

• 3ドル ≤ N ≤10^5$
• $ 0 ≤ M \le \min(10^5, 29N)$
• 1ドル \le u_i , v_i , x_j, y_j \le N+M $

노트

모든 상황에서 실은 서로 다른 두 개의 구슬을 연결할 때만 이용될 수 있다. 즉, 하나의 구슬에만 연결된 실이 존재해서는 안 된다.