[ABC233F] Swap and Sort

给你一个长度为 $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$.

[problemUrl]: https://atcoder.jp/contests/abc233/tasks/abc233_f $ (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` と出力せよ。

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 ``` 操作の回数を最小化する必要はないことに注意してください。