18919번 - Allowed Swaps 스페셜 저지다국어

You are given a permutation of length $N$ and a list of allowed swaps. Each swap is defined by two distinct integers between 1 and $N$, inclusive --- positions in the permutation that can be swapped.

Your task is to sort the permutation using no more than $5 \cdot 10^5$ allowed swaps or determine that it is impossible. Note that each allowed swap can be used more than once.

The first line contains a single integer $N$ --- the length of the permutation ($3 \le N \le 1000$).

The second line contains $N$ distinct integers between 1 and $N$, inclusive --- the permutation itself.

The third line contains a single integer $S$ ($1 \le S \le 2 \cdot 10^5$) --- the number of allowed swaps. Then $S$ lines follow, each containing two integers $p_i$ and $q_i$ ($1 \le p_i, q_i \le N$; $p_i \ne q_i$), denoting that elements on positions $p_i$ and $q_i$ can be swapped.

You may assume that no two allowed swaps coincide.

If it is impossible to sort the array using no more than $5 \cdot 10^5$ swaps from the given list, print $-1$. 

Otherwise, print the number of swaps used, $K$, followed by $K$ pairs of integers $x_j$ and $y_j$ ($1 \le x_j, y_j \le N$; $x_j \ne y_j$) describing the sequence of swaps. Each pair must belong to the list of allowed swaps (formally, for each $j$, there must exist $i$ such that either $x_j = p_i$ and $y_j = q_i$, or $x_j = q_i$ and $y_j = p_i$).

If there is more than one solution, print any of them. The number of swaps does not have to be minimized.