CF690F2 Tree of Life (medium)

Heidi 厌倦了解读生命之树中隐藏的预言，决定返回她的总部，休息一下并在那里尝试解读。当然，她无法连根拔起生命之树带回去，于是她在纸上画下了这棵树。再想想，她又画了更多一模一样的图，总共画了 $n$ 张（其中 $n$ 是生命之树的顶点数）——谁知道会发生什么呢？ 果然，在回去的路上，Heidi 遭遇了一群僵尸的伏击。虽然她成功击退了僵尸，但她的画被以一种奇特的方式损坏了：在第 $i$ 张副本中，编号为 $i$ 的顶点被移除了，同时与其相连的所有边也被删除。在每一张图中，僵尸还抹去了所有顶点的编号，并用 $1$ 到 $n$ 的数字对剩下的 $n-1$ 个顶点进行了任意重新编号（幸运的是，每个顶点仍然有唯一的编号）。更糟糕的是，这些画还被任意打乱了顺序。 现在 Heidi 想要根据她对所有画的描述（以边的列表形式）恢复出生命之树。

输入的第一行包含 $Z \leq 20$ —— 测试用例的数量。接下来是 $Z$ 个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$（$2 \leq n \leq 100$）和 $k$（其中 $k$ 是画的数量，满足 $k=n$）。接下来的若干行给出了 $k$ 张画的描述。第 $i$ 张画的描述为一行，包含 $m_i$ —— 该画中的边数，接下来有 $m_i$ 行，每行描述一条边，包含两个用空格分隔的整数，表示该边连接的两个顶点编号。

如果 Heidi 的画不可能来自同一棵树，则输出一行 NO。否则，输出一行 YES，接下来 $n-1$ 行描述 Heidi 的画可能来自的任意一棵树。对于每条边，输出其连接的两个顶点编号，编号之间用一个空格分隔。如果有多种解，输出任意一种即可。

由 ChatGPT 4.1 翻译