题目描述

同构性问题旨在检验两个图是否本质上相同。假设给定一组图，需要对每个图执行某种操作。若能识别出哪些图是重复的，就可将其舍弃，从而避免冗余工作。

首先要解释两个图“相同”的含义。当能找到一个从图 $G_1=(V_1, E_1)$ 的顶点到图 $G_2=(V_2, E_2)$ 的顶点的映射 $f$，使得 $(x, y)$ 是 $G_1$ 的一条边当且仅当 $(f(x), f(y))$ 是 $G_2$ 的一条边时，这两个带标签的图 $G_1$ 和 $G_2$ 是相同的。这样的映射被称为同构映射。

对于一般的图同构问题，目前还没有已知的高效算法，但判断两棵树是否同构相对容易。在$图 7$ 中，不难验证树 $T_1$ 与树 $T_3$ 同构，但 $T_1$ 与 $T_2$ 不同构。

给定一组 $k$ 棵树 $C = \{T_1, T_2, \cdots, T_k\}$，每棵树 $T_i$ 恰好有 $n$ 个节点。本题的目标是将这些树划分为同构类，使得同一同构类中的任意两棵树彼此同构。

一种简单的方法是枚举所有可能的映射函数，这需要生成 $n!$ 种不同的映射。其结果是，仅测试两棵树就会得到一个非常耗时的 $O(n!)$ 时间复杂度的算法。你需要想出一个更巧妙的方法来解决这个问题。

输入

一组 $k$ 棵（每棵树有 $n$ 个节点）的树 $C = \{T_1, T_2, \cdots, T_k\}$。输入是一个整数列表。前两个整数（在同一行）分别表示树的数量 $k$ 和每棵树的节点数 $n$。注意，$k$ 最大可达 $150$，$n$ 最大可达 $100$。在这两个整数之后，会有 $k$ 行，每行表示每棵树 $T_i$ 的边集；每行恰好包含 $n - 1$ 对整数，代表每棵树的 $n - 1$ 条（有向）边。因此，每棵树共有 $2n - 2$ 个整数，除了前两个参数外，总输入将有 $2k(n - 1)$ 个整数。每棵树按其出现的顺序编号；即，第一行表示树 $T_1$，第二行表示 $T_2$，以此类推，最后（第 $k$ 行）表示 $T_k$。

输出

对于给定的树集合，将这些树划分为同构类，使得同一同构类中的任意两棵树彼此同构。对于每个同构类，在一行中输出这些同构树的编号。假设共有 $m$ 个同构类，你需要输出 $m$ 行。例如，一行

$t_1 = t_2 = \cdots = t_p;$

表示一个大小为 $p$ 的同构类，其中两棵树 $T_{t_i}$ 和 $T_{t_j}$（$1\leq i, j \leq p$）彼此同构。对于每一行，按升序输出那些同构树的编号；即，$t_1 < t_2 < \cdots < t_p$。此外，按字典序升序输出这 $m$ 个同构类；即，按它们第一个编号的顺序输出。例如，假设存在 $4$ 个同构类 $\{4, 2, 7\}$、$\{5, 1, 3\}$、$\{8, 9\}$、$\{6\}$，输出应为

$1 = 3 = 5 ;$

$2 = 4 = 7 ;$

$6 ;$

$8 = 9 ;$

输入样例

3 7
7 2 7 1 7 6 2 3 1 4 6 5
7 2 7 1 2 3 1 4 1 5 5 6
4 3 3 2 4 1 1 7 5 6 4 5

输出样例

1 = 3 ;
2 ;

题目来源

台湾 2002 年竞赛题目