목걸이 만들기

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

민준이는 물질적인 선물을 좋아하므로, 창현이는 고백할 때 선물로 줄 목걸이를 만들기로 했다. 창현이에게는 $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 \le N \le 10^5$

$0 \le M \le \min(10^5, 29N)$

$1 \le u_i, v_i, x_j, y_j \le N+M$

시간 제한은 1000 ms, 메모리 제한은 1024 MB이다.