Sorting with allowed swaps

You are given a permutation of the numbers 1 to $N$, where every number appears once.

You are also given $Q$ pairs of positions $(a, b)$. Each pair means you may swap the number at position $a$ with the number at position $b$, and you may use the same pair many times.

Decide whether the allowed swaps can sort the permutation into increasing order. If they can, print the swap sequence defined by the rule in the output section. You may not use more than 500000 swaps.

The first line has the length of the permutation $N$ ($1 \le N \le 1000$).

The second line has $N$ distinct integers between 1 and $N$, the permutation itself.

The third line has the number of allowed swaps $Q$ ($1 \le Q \le 200000$).

Each of the next $Q$ lines has two positions $a$ and $b$ that may be swapped. Both are between 1 and $N$, and they differ. The same pair can appear several times, and the two positions can come in either order.

If the allowed swaps cannot sort the permutation, print NEMOGUCE on the first line.

Otherwise print the swaps that the following rule produces, one per line, in the order the rule produces them. A permutation can usually be sorted in many ways, so only the sequence this rule produces is accepted.

1. Build a graph whose vertices are the positions 1 to $N$ and whose edges are the given pairs. Scan the edges in input order. If the two endpoints are not connected yet, add the edge to a forest $F$, otherwise drop it. $F$ then holds a spanning tree of every connected component.
2. Let $S$ be the set of remaining positions, starting at $\{1, 2, \dots, N\}$. Repeat the following until $S$ is empty.
   1. Among the vertices of $S$ that have at most one neighbor of $S$ in $F$, let $u$ be the one with the smallest number. Such a vertex always exists.
   2. If position $u$ does not hold the value $u$, let $p$ be the position that holds the value $u$. Inside $F$ restricted to $S$, the path between $p$ and $u$ is unique. Walk that path from $p$ toward $u$, swap the values of each neighboring pair of positions on the path in turn, and print those two positions for every swap.
   3. Remove $u$ from $S$.
3. Print one swap per line, writing the two swapped positions in increasing order, separated by one space. If no swap is needed, print nothing.

The rule uses at most $N(N-1)/2$ swaps, so the number of swaps never exceeds 500000.