{"problem":{"name":"Swap and Sort","description":{"content":"We have a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$. There are $M$ kinds of operations available to you. Operation $i$ swaps the $a_i$\\-th and $b_i$\\-th elements of $P$. Is it possible ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc233_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc233_f","tags":[],"sample_group":[["6\n5 3 2 4 6 1\n4\n1 5\n5 6\n1 2\n2 3","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)$."],["5\n3 4 1 2 5\n2\n1 3\n2 5","\\-1\n\nWe cannot sort $P$ in ascending order."],["4\n1 2 3 4\n6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4","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."]],"created_at":"2026-03-03 11:01:14"}}