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.

제한

힌트