{"problem":{"name":"Number of Cycles","description":{"content":"In this problem, a permutation of $(1,2,\\cdots,N)$ is occasionally called just a permutation. For a permutation $a=(a_1,a_2,\\cdots,a_N)$, let $f(a)$ be the number of cycles in $a$. More accurately, th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc060_e"},"statements":[{"statement_type":"Markdown","content":"In this problem, a permutation of $(1,2,\\cdots,N)$ is occasionally called just a permutation.\nFor a permutation $a=(a_1,a_2,\\cdots,a_N)$, let $f(a)$ be the number of cycles in $a$. More accurately, the value of $f(a)$ is defined as follows.\n\n*   Consider an undirected graph consisting of $N$ vertices numbered $1$ to $N$. For each $1 \\leq i \\leq N$, add an edge connecting vertex $i$ and vertex $a_i$. Then, let $f(a)$ be the number of connected components in this graph.\n\nYou are given a permutation $P=(P_1,P_2,\\cdots,P_N)$ and an integer $K$. Determine whether there is a permutation $x$ that satisfies the following condition, and construct one if it exists.\n\n*   Let $y_i=P_{x_i}$ to define a permutation $y$.\n*   Then, $f(x)+f(y)=K$ holds.\n\nFor each input file, solve $T$ test cases.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $2 \\leq K \\leq 2N$\n*   $(P_1,P_2,\\cdots,P_N)$ is a permutation of $(1,2,\\cdots,N)$.\n*   In each input file, the sum of $N$ does not exceed $2 \\times 10^5$.\n*   All numbers in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is in the following format:\n\n$N$ $K$\n$P_1$ $P_2$ $\\cdots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc060_e","tags":[],"sample_group":[["3\n3 3\n1 3 2\n2 2\n2 1\n4 8\n1 2 3 4","Yes\n2 1 3\nNo\nYes\n1 2 3 4\n\nIn the first case, letting $x=(2,1,3)$ makes $y=(3,1,2)$, satisfying $f(x)+f(y)=2+1=3$."]],"created_at":"2026-03-03 11:01:14"}}