2033E.md (2024B)
1 Source: https://codeforces.com/problemset/problem/2033/E 2 3 E. Sakurako, Kosuke, and the Permutation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Sakurako's exams are over, and she did excellently. As a reward, she received a permutation $p$. Kosuke was not entirely satisfied because he failed one exam and did not receive a gift. He decided to sneak into her room (thanks to the code for her lock) and spoil the permutation so that it becomes simple. 22 23 A permutation $p$ is considered simple if for every $i$ $(1\le i \le n)$ one of the following conditions holds: 24 25 * $p_i=i$ 26 * $p_{p_i}=i$ 27 28 For example, the permutations $[1, 2, 3, 4]$, $[5, 2, 4, 3, 1]$, and $[2, 1]$ are simple, while $[2, 3, 1]$ and $[5, 2, 1, 4, 3]$ are not. 29 30 In one operation, Kosuke can choose indices $i,j$ $(1\le i,j\le n)$ and swap the elements $p_i$ and $p_j$. 31 32 Sakurako is about to return home. Your task is to calculate the minimum number of operations that Kosuke needs to perform to make the permutation simple. 33 34 Input 35 36 The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. 37 38 Each test case is described by two lines. 39 40 * The first line contains one integer $n$ ($1\le n \le 10^6$) — the length of the permutation $p$. 41 * The second line contains $n$ integers $p_i$ ($1\le p_i\le n$) — the elements of the permutation $p$. 42 43 It is guaranteed that the sum of $n$ across all test cases does not exceed $10^6$. 44 45 It is guaranteed that $p$ is a permutation. 46 47 Output 48 49 For each test case, output the minimum number of operations that Kosuke needs to perform to make the permutation simple. 50 51 Example 52 53 Input 54 55 ``` 56 6 57 58 5 59 60 1 2 3 4 5 61 62 5 63 64 5 4 3 2 1 65 66 5 67 68 2 3 4 5 1 69 70 4 71 72 2 3 4 1 73 74 3 75 76 1 3 2 77 78 7 79 80 2 3 1 5 6 7 4 81 ``` 82 83 Output 84 85 ``` 86 0 87 0 88 2 89 1 90 0 91 2 92 ``` 93 94 Note 95 96 In the first and second examples, the permutations are already simple. 97 98 In the fourth example, it is sufficient to swap $p_2$ and $p_4$. Thus, the permutation will become $[2, 1, 4, 3]$ in $1$ operation.