CF690F2.Tree of Life (medium)

Heidi got tired of deciphering the prophecy hidden in the Tree of Life and decided to go back to her headquarters, rest a little and try there. Of course, she cannot uproot the Tree and take it with her, so she made a drawing of the Tree on a piece of paper. On second thought, she made more identical drawings so as to have n in total (where n is the number of vertices of the Tree of Life) – who knows what might happen?

Indeed, on her way back Heidi was ambushed by a group of zombies. While she managed to fend them off, they have damaged her drawings in a peculiar way: from the i-th copy, the vertex numbered i was removed, along with all adjacent edges. In each picture, the zombies have also erased all the vertex numbers and relabeled the remaining n - 1 vertices arbitrarily using numbers 1 to n (fortunately, each vertex still has a distinct number). What's more, the drawings have been arbitrarily shuffled/reordered.

Now Heidi wants to recover the Tree of Life from her descriptions of all the drawings (as lists of edges).

海蒂厌倦了破译生命之树中隐藏的预言，决定返回总部稍作休息，再尝试破解。当然，她无法将生命之树连根拔起带走，于是她在一张纸上画出了这棵树的示意图。再三考虑后，她又绘制了若干张完全相同的图，最终共得到 $n$ 张（其中 $n$ 为生命之树的顶点数）——谁又能预料会发生什么呢？

果然，在返程途中，海蒂遭到了一群僵尸的伏击。虽然她成功击退了这些僵尸，但它们却以一种奇特的方式损坏了她的图纸：在第 $i$ 张图上，编号为 $i$ 的顶点及其所有邻接边均被移除。此外，每张图上的所有顶点编号均被僵尸擦除，并将剩余的 $n-1$ 个顶点任意地重新标号为 $1$ 至 $n$ 中的数字（幸运的是，每个顶点仍具有互不相同的编号）。更糟糕的是，这些图纸还被僵尸随意打乱了顺序。

现在，海蒂希望仅凭她对所有图纸的描述（即每张图的边集列表），还原出原始的生命之树。

The first line of the input contains Z ≤ 20 – the number of test cases. Z descriptions of single test cases follow.

In each test case, the first line of input contains numbers n (2 ≤ n ≤ 100) and k (where k is the number of drawings; we have k = n). In the following lines, the descriptions of the k drawings are given. The description of the i-th drawing is a line containing m__i – the number of edges in this drawing, followed by m__i lines describing edges, each of which contains two space-separated integers –- the numbers of the two vertices connected by the edge.

输入的第一行包含一个整数 $Z \leq 20$，表示测试用例的数量。随后是 $Z$ 个测试用例的描述。

对于每个测试用例，输入的第一行包含两个整数 $n$（$2 \leq n \leq 100$）和 $k$（其中 $k$ 表示绘图次数；本题中恒有 $k = n$）。接下来的若干行给出 $k$ 次绘图的描述。第 $i$ 次绘图的描述由一行开始，该行包含一个整数 $m_i$ —— 表示该次绘图中的边数；随后是 $m_i$ 行，每行描述一条边，包含两个以空格分隔的整数 —— 即该边所连接的两个顶点的编号。

If Heidi's drawings cannot possibly come from a single tree, you should output the word NO. Otherwise, output one line containing the word YES and n - 1 lines describing any tree that Heidi's drawings could have come from. For every edge you should output the numbers of the vertices that it connects, separated with a single space. If there are many solutions, print any of them.

如果海蒂的绘图不可能来自同一棵树，则应输出单词 NO。否则，输出一行单词 YES，再输出 $n-1$ 行，描述海蒂的绘图可能源自的任意一棵树。对于每条边，应输出其所连接的两个顶点的编号，中间用一个空格分隔。若存在多种解，输出任意一种即可。