English version of this editorial is provided after the Chinese version.
考虑 u \to P_u 所形成的若干个置换环，显然从前往后贪心选能选到的 A_i 最小的点。
假设目前已经贪心地选了 i-1 位，且 i 的取值尚未确定，则设 i 所在置换环长为 M，并从 i 开始，按 u \to P_u 的顺序为环上每个点从 0 开始标号。这是因为假设 j 是 i 所在置换环上的任意一点，编号为 \mathrm{num}_j，那么将 j 置换到 i 的位置上便需要 \mathrm{num}_j + kM,k \in \mathbb N 次置换。
设最优置换次数为 C，则如果在第 i 位填 A_j，则要求 C \equiv \mathrm{num}_j \pmod M。注意到这个方程不一定能成立，因为前面的贪心对 C 已经有了若干个限制。假设前面的限制可以合并为一个同余方程，那我们显然可以通过求 gcd \mathrm{O}(\log N) 判断是否与当前方程冲突。但是这样的话需要求环长的 lcm，会爆 ___int128。
题解的解决办法是用 python 的自带高精度，但是作为 C++ 选手，我们还有另外的做法。
假设环的个数为 K，环长序列为 Q，那么不可重集 \{Q_1,Q_2,\cdots,Q_K\} 的大小是 \mathrm{O}(\sqrt{N}) 的（这是因为 \sum_{i=1}^K Q_i = N）。假设第 i 个环对 C 的限制形如 C \equiv c_i \pmod{Q_i}，那么有 Q_i=Q_j \Rarr c_i = c_j。于是我们的本质不同方程个数便只有 \mathrm{O}(\sqrt{N}) 个，且若新加一个方程，整个方程组解集不为空的充要条件是该方程与方程组中任意方程都有公共解，暴力判断即可。
时间复杂度 \mathrm{O}(N \sqrt{N} \log N)，实际跑的非常快。
Consider the permutation cycles formed by u \to P_u. It is evident that we should greedily select the smallest possible A_i from front to back.
Assume that we have already greedily selected i-1 positions, and the value of i is yet to be determined. Let the length of the permutation cycle containing i be M, and label each point in the cycle starting from i in the order of u \to P_u, beginning from 0. This is because if j is any point in the permutation cycle containing i, with a label \mathrm{num}_j, then moving j to the position of i requires \mathrm{num}_j + kM, k \in \mathbb{N} permutations.
Let the optimal number of permutations be C. If we fill A_j at position i, then C \equiv \mathrm{num}_j \pmod{M}. Note that this equation may not always hold, as the previous greedy selections have already imposed several constraints on C. If the previous constraints can be combined into a single congruence equation, we can determine if it conflicts with the current equation by calculating the gcd \mathrm{O}(\log N). However, this requires calculating the lcm of the cycle lengths, which can overflow ___int128.
The solution provided in the problem uses Python's built-in high precision, but as C++ programmers, we have another approach.
Assume there are K cycles, with cycle lengths given by Q. The size of the unique set {Q_1, Q_2, \cdots, Q_K} is \mathrm{O}(\sqrt{N}) (since \sum_{i=1}^K Q_i = N). Suppose the constraint on C from the i-th cycle is C \equiv c_i \pmod{Q_i}, then Q_i = Q_j \Rightarrow c_i = c_j. Thus, the number of essentially different equations is only \mathrm{O}(\sqrt{N}), and if a new equation is added, the necessary and sufficient condition for the solution set of the entire system to be non-empty is that the new equation has a common solution with every equation in the system, which can be checked by brute force.
The time complexity is \mathrm{O}(N \sqrt{N} \log N), and it runs very fast in practice.