#P18107. Leave Triple & Link Tree
Leave Triple & Link Tree
Leave Triple & Link Tree
给定 个三元组,每个三元组中的三个整数互不相同,且都在 到 之间。保证每个整数在全部三元组中总共恰好出现三次。
你需要执行如下操作:
- 删除其中一个三元组。
- 对于剩余的每个三元组,删除其中一个整数,留下两个整数。
将最终的 对整数视为无向图的边,顶点为 。要求这张图连通。
请构造一种满足要求的方案,或说明不存在。如果有多种方案,必须使被完整删除的三元组的原始编号最大。在这个条件下仍有多种方案时,可以输出任意一种。
输入格式
第一行包含测试数据组数 ,其中 。
每组数据第一行包含整数 ,其中 。
接下来 行,每行包含三个整数 ,其中 ,且同一行的三个数两两不同。
保证每个整数 在这 行中恰好出现三次。不同的三元组允许完全相同。
所有测试组的 之和不超过 。
输出格式
对于每组数据,如果不存在方案,输出一行 NO。
否则先输出一行 YES,再输出 行,第 行描述第 个三元组的处理结果:
- 如果完整删除该三元组,输出
-1 -1。 - 否则输出保留下来的两个整数,顺序任意。
必须恰好完整删除一个三元组,并使其编号在所有可行方案中最大。
样例
输入:
2
9
1 2 3
9 8 7
6 8 7
5 1 4
6 9 2
3 5 7
2 4 6
4 3 1
9 5 8
6
1 3 2
1 3 2
1 3 2
4 5 6
4 5 6
4 5 6
一种合法输出:
YES
2 3
9 8
8 7
5 1
6 9
3 5
2 6
4 1
-1 -1
NO