近视后入

这题并不是所有的环都可以计为环。在图片中类型为 C 的纯环才算。为什么？因为别的环它里面有入度 $\ge 2$ 的元素（即 F 类联通分量），于是我们可以将一个元素转化为另一个最终结果相同的元素，此时环被切断，我们得到了一个无环的联通分量，所以 F 类联通分量不计入环（计入环说明这个联通分量需要额外的一部操作来将其完全转化）。

首先，我们定义 $G$ 是由 $S$ 中每个字符映射到 $T$ 中对应的字符所组成的有向映射所组成的图。

让我们考虑初始图 $G$ 和棋子的分布。每个连通分量属于以下六种类型之一：

A：孤立顶点

B：长度为 1 的环

C：长度为 2 或更长的环

D：有根树

E：长度为 1 的环，以及以该环为根的有根树

F：长度为 2 或更长的环，以及连接到环中顶点的有根树

直接给出结论，答案如下：

如果 $G$ 由零个或多个类型 B 的连通分量以及一个或多个类型 C 的连通分量组成，则答案为 $−1$。

否则，答案是目标位置与初始顶点不同的棋子数量，加上类型 C 的连通分量的数量。即，答案为 $N−(a+b+d+e)+c$，其中 $x$ 表示类型 $x$ 的连通分量的数量。

对于前一种情况，“$G$ 由零个或多个类型 B 的连通分量以及一个或多个类型 C 的连通分量组成”当且仅当“($A_a,A_b,…,A_z$) 是 ($A_a,A_b,…,A_z$) 的一个排列，且 $S\neq T$”，其中 $A_c$ 是从顶点 $c$ 出发的边指向的顶点（如果不存在这样的边，则为 $−1$）。对于后一种情况，为了计算类型 C 的连通分量的数量，只需统计大小为 $2$ 或更大且每个顶点的入度不超过 $1$ 的连通分量。由于 $G$ 的顶点数不超过 $26$，只要算法在多项式时间内运行，几乎任何解法都能通过。

最后，我们简要证明结论的正确性。

前一种情况的合理性在于，第一次执行操作时，会将两个目标位置不同的棋子移动到同一个顶点上。

对于第二种情况，我们可以证明该值是一个下界：任何目标位置与初始顶点不同的棋子至少需要一次操作，而对于类型 C 的连通分量，无法在少于棋子数量的操作次数内将所有棋子移动到目标位置（直观上，至少有一个棋子需要“暂存”到另一个顶点）。

对于第二种情况，我们可以通过实际构造操作步骤来证明该值是一个上界。首先，对于类型 A、B、D 和 E 的连通分量，按照从根到叶的顺序将每个棋子移动到其目标位置。对于类型 F 的连通分量，可以选择环中的一个顶点，将其棋子移动到环外某个未被占用且目标位置相同的顶点，从而将其转化为类型 D 的情况。最后，对于类型 C 的情况，可以将任意一个棋子移动到一个未被占用的顶点（通过处理类型 A、D、E 和 F 的连通分量腾出的空间），从而将其转化为类型 D 的情况。