시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 42 11 11 32.353%

문제

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.

예제 입력 1

4
4 1 2 3
4
1 2
2 3
3 4
4 1

예제 출력 1

3
4 1
1 2
2 3

예제 입력 2

4
1 3 4 2
2
2 1
2 3

예제 출력 2

-1