题目描述

$(1,2,\ldots,N)$ を並び替えた長さ $N$ の順列 $P=(P_1,P_2,\ldots,P_N)$ があります。

あなたが可能な操作は $M$ 種類あり、操作 $i$ は「 $P$ の $a_i$ 番目の要素と $P$ の $b_i$ 番目の要素を入れ替える」というものです。

操作を好きな順序で、合計 $5\times\ 10^5$ 回以下行うことによって、$P$ を昇順に並び替えることはできますか？

できるならば、操作手順を $1$ つ教えてください。できないならばその旨を伝えてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出格式

$P$ を昇順に並び替えることができるならば以下の形式で出力せよ。

$K$ $c_1$ $c_2$ $\ldots$ $c_K$

ここで、$K$ は操作の回数を表し、$c_i(1\leq\ i\ \leq\ K)$ は $i$ 回目に行う操作が操作 $c_i$ であることを表す。
$0\leq\ K\ \leq\ 5\times\ 10^5$ を満たさなければならないことに注意せよ。

$P$ を昇順に並び替えることができないならば、-1 と出力せよ。

题目大意

给你一个长度为 $n$ 的排列和 $m$ 种操作. 每个操作形如 $(u,v)$ , 表示将 $a_u$ 和 $a_v$ 交换 .

请问是否存在一种方案, 经过适当操作, 把这个排列变为 $(1,2,3,\dots,n)$? 如果可以, 请给出一种构造, 要求长度不超过 $5 \times 10^5$. 否则请输出 $-1$.

$n \le 10^3 , m \le 2 \times 10^5$.

6
5 3 2 4 6 1
4
1 5
5 6
1 2
2 3

3
4 2 1

5
3 4 1 2 5
2
1 3
2 5

-1

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

0

提示

制約

• $2\leq\ N\ \leq\ 1000$
• $P$ は $(1,2,\ldots,N)$ を並び替えた順列
• $ 1\leq\ M\ \leq\ \min(2\times\ 10^5,\ \frac{N(N-1)}{2}) $
• $1\leq\ a_i\ \lt\ b_i\leq\ N$
• $i\neq\ j$ ならば $(a_i,b_i)\neq\ (a_j,b_j)$
• 入力に含まれる値は全て整数

Sample Explanation 1

$P$ は、$ (5,3,2,4,6,1)\to\ (5,2,3,4,6,1)\to\ (5,2,3,4,1,6)\to\ (1,2,3,4,5,6) $ と変化します。

Sample Explanation 2

$P$ を昇順に並び替えることはできません。

Sample Explanation 3

初めから $P$ が昇順に並んでいることもあります。 また、以下のような答えも正解になります。 4 5 5 5 5 操作の回数を最小化する必要はないことに注意してください。