허용된 교환으로 정렬하기

1부터 $N$까지의 수가 한 번씩 나오는 순열이 주어진다.

또 위치 쌍 $(a, b)$가 $Q$개 주어진다. 각 쌍은 $a$번 위치의 수와 $b$번 위치의 수를 교환할 수 있다는 뜻이고, 같은 쌍을 여러 번 사용해도 된다.

허용된 교환만 사용해 순열을 오름차순으로 정렬할 수 있는지 판정하고, 정렬할 수 있으면 출력 규칙이 정하는 교환 순서를 출력한다. 교환은 500000번을 넘게 사용할 수 없다.

첫째 줄에 순열의 길이 $N$ ($1 \le N \le 1000$)이 주어진다.

둘째 줄에 1 이상 $N$ 이하의 서로 다른 정수 $N$개가 순열을 이루어 주어진다.

셋째 줄에 허용된 교환의 개수 $Q$ ($1 \le Q \le 200000$)가 주어진다.

이어지는 $Q$개 줄에 교환이 허용된 두 위치 $a$와 $b$가 주어진다. 두 수는 1 이상 $N$ 이하이고 서로 다르다. 같은 쌍이 여러 번 주어지기도 하고, 두 수의 순서가 바뀌어 주어지기도 한다.

허용된 교환으로 순열을 정렬할 수 없으면 첫째 줄에 NEMOGUCE를 출력한다.

정렬할 수 있으면 다음 규칙이 만드는 교환을 만들어진 순서대로 한 줄에 하나씩 출력한다. 순열을 정렬하는 방법은 보통 여러 가지이므로 이 규칙이 만드는 교환 순서만 정답으로 인정한다.

1. 위치 1부터 $N$까지를 정점으로, 입력에 주어진 쌍을 간선으로 하는 그래프를 생각한다. 간선을 입력에 주어진 순서대로 살펴보면서 두 끝점이 아직 연결되지 않았으면 그 간선을 숲 $F$에 넣고, 이미 연결되어 있으면 버린다. 그러면 $F$는 각 연결 요소의 신장 트리로 이루어진다.
2. 남은 위치의 집합 $S$를 $\{1, 2, \dots, N\}$으로 둔다. $S$가 빌 때까지 다음을 반복한다.
   1. $S$에 속한 정점 가운데 $F$에서 $S$에 속한 이웃이 1개 이하인 정점을 모으고, 그중 번호가 가장 작은 정점을 $u$라고 한다. 이런 정점은 항상 있다.
   2. 위치 $u$에 값 $u$가 없으면, 값 $u$가 놓인 위치를 $p$라고 한다. $S$에 속한 정점만 남긴 $F$에서 $p$와 $u$를 잇는 경로는 유일하다. 이 경로를 $p$에서 $u$ 쪽으로 따라가며 경로 위에서 이웃한 두 위치의 값을 차례로 교환하고, 교환할 때마다 그 두 위치를 출력한다.
   3. $S$에서 $u$를 뺀다.
3. 교환 한 번을 한 줄에 출력하고, 한 줄에는 교환한 두 위치를 작은 값, 큰 값 순서로 공백 하나를 사이에 두고 쓴다. 교환이 한 번도 필요하지 않으면 아무것도 출력하지 않는다.

이 규칙은 교환을 최대 $N(N-1)/2$번 사용하므로 교환 횟수는 항상 500000 이하다.