思路

注意到，我们设

有

发现，当固定

可以发现，所有的$g(y)$ 也固定了

所以，枚举 $t$ ，固定 $f(t)=1$，再枚举 $y$，得到所有$g(y)$，如果匹配不上就舍弃这个 $t$

然后，按照 $g(y)$ 计算 $f(x)$，直接 $O(n^2)$ 即可

把 $f$ 和 $g$ 分别看成 $n$ 元排列。每个排列可以分解成若干置换环，一个长 $k$ 的环需要 $k-1$ 次交换归位

所以显然有：

• 行交换次数 $= n - \text{环数}(f)$
• 列交换次数 $= n - \text{环数}(g)$
• 总次数 $= 2n - \text{环数}(f) - \text{环数}(g)$

置换环：从 $i$ 出发，不断跳 $i \to f(i) \to f(f(i)) \to \dots$ 直到回到起点，走过的点构成一个环。每个环数一次，标记已访问