{"problem":{"name":"Good Permutation","description":{"content":"In this problem, when we say just a \"permutation\", it refers to a permutation of $(1,2,\\dots,N)$. You are given a permutation $P=(P_{1},P_{2},\\dots,P_{N})$. A permutation $Q=(Q_{1},Q_{2},\\dots,Q_{N})$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc167_d"},"statements":[{"statement_type":"Markdown","content":"In this problem, when we say just a \"permutation\", it refers to a permutation of $(1,2,\\dots,N)$.\nYou are given a permutation $P=(P_{1},P_{2},\\dots,P_{N})$.\nA permutation $Q=(Q_{1},Q_{2},\\dots,Q_{N})$ is said to be a good permutation when the following holds.\n\n*   For every integer $1\\leq x\\leq N$, it is possible to make $x$ equal $1$ by repeating the substitution $x\\leftarrow Q_{x}$ some number of times.\n\nYou want to make $P$ a good permutation by performing the following operation on $P$ zero or more times.\n\n*   Choose integers $i$ and $j$ such that $1\\leq i\\lt j \\leq N$, and swap $P_{i}$ and $P_{j}$.\n\nLet $M$ be the minimum number of times you must perform the operation to make $P$ a good permutation. Find the lexicographically smallest good permutation that can be obtained by performing the operation $M$ times on $P$.\nFor each input file, you have $T$ test cases to solve.\nWhat is lexicographical order on sequences?A sequence $S = (S_1,S_2,\\ldots,S_{|S|})$ is said to be **lexicographically smaller** than a sequence $T = (T_1,T_2,\\ldots,T_{|T|})$ when one of the following 1. or 2. holds. Here, $|S|$ and $|T|$ denote the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1,S_2,\\ldots,S_{|S|}) = (T_1,T_2,\\ldots,T_{|S|})$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ that satisfies both of the following.\n    *   $(S_1,S_2,\\ldots,S_{i-1}) = (T_1,T_2,\\ldots,T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number).\n\n## Constraints\n\n*   $1\\leq T\\leq 10^{5}$\n*   $2\\leq N\\leq 2\\times 10^{5}$\n*   $(P_{1},P_{2},\\dots ,P_{N})$ is a permutation of $(1,2,\\dots ,N)$.\n*   For each input file, the sum of $N$ does not exceed $2\\times 10^{5}$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_{1}$\n$\\text{case}_{2}$\n$\\vdots$\n$\\text{case}_{T}$\n\nEach case is given in the following format:\n\n$N$\n$P_{1}$ $P_{2}$ $\\cdots$ $P_{N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc167_d","tags":[],"sample_group":[["5\n4\n2 1 4 3\n5\n2 1 3 4 5\n2\n1 2\n2\n2 1\n9\n4 3 6 2 7 1 9 8 5","2 3 4 1\n2 3 4 5 1\n2 1\n2 1\n4 3 5 2 7 1 8 9 6\n\nFor the first test case:\n$P$ is not a good permutation. Swapping $P_{1}$ and $P_{3}$ makes $P=(4,1,2,3)$, which is a good permutation, so $M=1$. Other than that, swapping $P_{2}$ and $P_{4}$ makes $P=(2,3,4,1)$, which is the lexicographically smallest good permutation that can be obtained in $M=1$ operation, so this is the answer."]],"created_at":"2026-03-03 11:01:14"}}