{"raw_statement":[{"iden":"problem statement","content":"We have a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$.\nThere are $M$ kinds of operations available to you. Operation $i$ swaps the $a_i$\\-th and $b_i$\\-th elements of $P$.\nIs it possible to sort $P$ in ascending order by doing at most $5\\times 10^5$ operations in total in any order?\nIf it is possible, give one such sequence of operations. Otherwise, report so."},{"iden":"constraints","content":"*   $2\\leq N \\leq 1000$\n*   $P$ is a permutation of $(1,2,\\ldots,N)$.\n*   $1\\leq M \\leq \\min(2\\times 10^5, \\frac{N(N-1)}{2})$\n*   $1\\leq a_i \\lt b_i\\leq N$\n*   $(a_i,b_i)\\neq (a_j,b_j)$ if $i\\neq j$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n$M$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\vdots$\n$a_M$ $b_M$"},{"iden":"sample input 1","content":"6\n5 3 2 4 6 1\n4\n1 5\n5 6\n1 2\n2 3"},{"iden":"sample output 1","content":"3\n4 2 1\n\n$P$ changes as follows: $(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)$."},{"iden":"sample input 2","content":"5\n3 4 1 2 5\n2\n1 3\n2 5"},{"iden":"sample output 2","content":"\\-1\n\nWe cannot sort $P$ in ascending order."},{"iden":"sample input 3","content":"4\n1 2 3 4\n6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4"},{"iden":"sample output 3","content":"0\n\n$P$ may already be sorted in ascending order.\nAdditionally, here is another accepted output:\n\n4\n5 5 5 5\n\nNote that it is not required to minimize the number of operations."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}