海蒂厌倦了破译隐藏在生命之树中的预言,决定回到总部,休息一下,然后去尝试一下。当然,她不能把树连根拔起并随身携带,所以她在一张纸上画了树的图画。再想一想,她又画了更多相同的图画,总共有 n 个(其中 n 是生命之树的顶点数)——谁知道会发生什么?
确实,海蒂在回来的路上遭到了一群丧尸的伏击。虽然她设法抵御它们,但它们以一种特殊的方式损坏了她的图画:从第 i 个副本中,编号为 i 的顶点以及所有相邻的边都被删除了。在每张图片中,僵尸还擦除了所有顶点编号,并使用数字 1 到 n 任意重新标记了剩余的 n - 1 个顶点(幸运的是,每个顶点仍然具有不同的编号)。更重要的是,图纸被任意打乱/重新排序。
现在海蒂想要从她对所有图画的描述(作为边缘列表)中恢复生命之树。
输入
输入的第一行包含 Z ≤ 20 – 测试用例的数量。下面是单个测试用例的 Z 描述。
在每个测试用例中,输入的第一行包含数字 n (2 ≤ n ≤ 100) 和 k(其中 k 是图纸数量;我们有 k = n)。下面给出k张图的描述。第i张图的描述是一条包含mi的行——该图中的边的数量,后面是mi行描述边,每条线包含两个空格分隔的整数——边连接的两个顶点的数量。
输出
如果海蒂的图画不可能来自一棵树,那么您应该输出“NO”一词。否则,输出包含单词 YES 的一行和描述 Heidi 的图画可能来自的任何树的 n - 1 行。对于每条边,您应该输出它连接的顶点的数量,并用一个空格分隔。如果有很多解决方案,请打印其中任何一个。
示例
输入 #1
1 5 5 2 4 1 2 1 1 3 1 3 4 1 4 3 2 1 3 3 1 3 2 4 1 3 2 1 3 2 4 2
输出 #1
YES 2 5 4 2 3 2 5 1