26439번 - Level Design 서브태스크다국어

문제

A permutation cycle in a permutation $C$ is a sequence of integers $(a_1, a_2, \dots, a_k)$ such that the following hold:

• $a_i \in C$ for all $i,ドル and are distinct.
• For each $i \in \{1, 2, \ldots, k-1\}$: $C[a_i] = a_{i+1},ドル and $C[a_k] = a_1$.

A permutation cycle of length $k$ is called a $k$-cycle.

For example, the permutation $C = [4, 2, 1, 3]$ has two cycles: the 3ドル$-cycle $(4, 3, 1),ドル and the 1ドル$-cycle $(2)$. $(4, 3, 1)$ is a cycle because $C[4] = 3,ドル $C[3] = 1,ドル and $C[1] = 4$.

Grace loves permutation cycles, so Charles decides to design an $\mathbf{N}$-level game to challenge her.

At the start of the game, the player is given an $\mathbf{N}$-length permutation $\mathbf{P}$ of integers from 1ドル$ through $\mathbf{N}$. The levels in the game are numbered from 1ドル$ to $\mathbf{N}$. At each level, the player starts with the given permutation, and is allowed to make modifications to it by swapping any two elements in it (multiple swaps allowed). To clear the $k$-th level in the game, the player is required to find the minimum number of swaps using which a $k$-cycle can be created in the permutation. The player can progress to the $(k+1)$-th level only after clearing the $k$-th level.

Grace finds the game a bit challenging, but wants to win at any cost. She needs your help! Formally, for each level $k,ドル you need to find the minimum number of swaps using which a $k$-cycle can be created in the permutation.

입력

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains an integer $\mathbf{N}$: the length of the permutation.

The next line contains $\mathbf{N}$ integers $\mathbf{P_1},ドル $\mathbf{P_2},ドル $\dots,ドル $\mathbf{P_N},ドル where the $i$-th integer represents the $i$-th element in the permutation $\mathbf{P}$.

출력

For each test case, output one line containing Case #x: S1, S2, ..., SN, where $x$ is the test case number (starting from 1), and $S_i$ is the solution for the $i$-th level in the game, that is, the minimum number of swaps needed to create an $i$-cycle in the permutation.

제한

• 1ドル \le \mathbf{T} \le 100$.
• 1ドル \le \mathbf{P_i} \le \mathbf{N},ドル for all $i$.
• All $\mathbf{P_i}$ are distinct.

Test Set 1 (17점)

• 1ドル \le \mathbf{N} \le 10^3$.

Test Set 2 (22점)

• 1ドル \le \mathbf{N} \le 10^5$.

힌트