#P18107. Leave Triple & Link Tree

Leave Triple & Link Tree

Leave Triple & Link Tree

给定 nn 个三元组,每个三元组中的三个整数互不相同,且都在 11 到 nn 之间。保证每个整数在全部三元组中总共恰好出现三次。

你需要执行如下操作:

  1. 删除其中一个三元组。
  2. 对于剩余的每个三元组,删除其中一个整数,留下两个整数。

将最终的 n−1n-1 对整数视为无向图的边,顶点为 1,2,…,n1,2,\ldots,n。要求这张图连通。

请构造一种满足要求的方案,或说明不存在。如果有多种方案,必须使被完整删除的三元组的原始编号最大。在这个条件下仍有多种方案时,可以输出任意一种。

输入格式

第一行包含测试数据组数 tt,其中 1≤t≤1041\le t\le10^4。

每组数据第一行包含整数 nn,其中 3≤n≤2×1053\le n\le2\times10^5。

接下来 nn 行,每行包含三个整数 ai,bi,cia_i,b_i,c_i,其中 1≤ai,bi,ci≤n1\le a_i,b_i,c_i\le n,且同一行的三个数两两不同。

保证每个整数 1…n1\ldots n 在这 nn 行中恰好出现三次。不同的三元组允许完全相同。

所有测试组的 nn 之和不超过 2×1052\times10^5。

输出格式

对于每组数据,如果不存在方案,输出一行 NO。

否则先输出一行 YES,再输出 nn 行,第 ii 行描述第 ii 个三元组的处理结果:

  • 如果完整删除该三元组,输出 -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