P16900 [GKS 2022 #H] Level Design

在排列 $C$ 中，一个**置换循环**是一个整数序列 $(a_1, a_2, \ldots, a_k)$，满足以下条件： - 对所有 $i$，$a_i \in C$，且互不相同。 - 对每个 $i \in \{1, 2, \ldots, k-1\}$ 有 $C[a_i] = a_{i+1}$，且 $C[a_k] = a_1$。 长度为 $k$ 的置换循环称为 **$k$-循环**。 例如，排列 $C = [4, 2, 1, 3]$ 有两个循环：$3$-循环 $(4, 3, 1)$ 和 $1$-循环 $(2)$。$(4, 3, 1)$ 是一个循环，因为 $C[4] = 3$，$C[3] = 1$，且 $C[1] = 4$。 :::align{center}  ::: Grace 喜欢置换循环，于是 Charles 决定设计一个 $N$ 级游戏来挑战她。 游戏开始时，玩家会得到一个长度为 $N$ 的排列 $P$，其中包含整数 $1$ 到 $N$。游戏级数编号为 $1$ 到 $N$。在每个级别，玩家从给定的排列开始，并可以通过交换其中任意两个元素来修改它（可以进行多次交换）。要通关第 $k$ 级，玩家需要找出在排列中创建一个 $k$-循环所需的最小交换次数。玩家只有在通关第 $k$ 级后才能进入第 $(k+1)$ 级。 Grace 觉得这个游戏有点挑战性，但她不惜一切代价想要获胜。她需要你的帮助！形式化地说，对于每个级别 $k$，你需要求出在排列中创建一个 $k$-循环所需的最小交换次数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$：排列的长度。 下一行包含 $N$ 个整数 $P_1, P_2, \ldots, P_N$，其中第 $i$ 个整数表示排列 $P$ 中的第 $i$ 个元素。

对于每个测试用例，输出一行，格式为 `Case #x: S1 S2 ... SN`，其中 $x$ 是测试用例编号（从 $1$ 开始），$S_i$ 是游戏中第 $i$ 级的答案，即在排列中创建一个 $i$-循环所需的最小交换次数。

在样例 #1 中，给定排列中有三个 $1$-循环。因此，第一级可以用零次交换通关。要通关第二级，我们可以交换前两个元素得到排列 $[2, 1, 3]$，其中包含 $2$-循环 $(2, 1)$。要通关第三级，我们可以交换前两个元素，然后交换第二个和第三个元素，得到排列 $[2, 3, 1]$，其中包含 $3$-循环 $(2, 3, 1)$。 在样例 #2 中，如前所述，排列包含 $1$-循环 $(2)$。因此，通关第一级需要零次交换。要通关第二级，我们可以交换最后两个元素得到排列 $[4, 2, 3, 1]$，其中包含 $2$-循环 $(4, 1)$。由于排列中也有 $3$-循环 $(4, 3, 1)$，因此第三级也可以用零次交换通关。要通关第四级，我们可以交换第二个和第四个元素得到排列 $[4, 3, 1, 2]$，其中包含 $4$-循环 $(4, 2, 3, 1)$。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le P_i \le N$。 所有 $P_i$ 互不相同。 **测试集 1** $1 \le N \le 10^3$。 **测试集 2** $1 \le N \le 10^5$。 翻译由 DeepSeek V4 Pro 完成