Part I： 注意到查询的过程，每轮操作会断掉一个环，因此返回的结果为 $n - c$，其中 $c$ 为置换环数。

Part II： 考虑对于每对在同一个置换环内的点，将其交换拆开，显然枚举所有对并且能操作就操作，会让置换环数变为 $n$。这样操作次数为 $\Theta(n^2)$，可以通过 Subtask 2。

Part III： 考虑二分。我们对每个 $i$ 二分出前面的第一个 $j$，满足 $i,j$ 在同一个置换环内即可。那么我们需要一次查询，查询在 $0,1,\cdots, j$ 中有没有和 $i$ 在同一个置换环内的点。考虑构造 $p_1,p_2,\cdots,p_{j}, p_i, p_{j+1},p_{j+2}\cdots p_{i-1},p_0,p_{i+1},p_{i+2},\cdots$ 即可。