Leave Triple & Link Tree

给定 n 个三元组，每个三元组中的整数均在 1 到 n 之间。保证每个数字在所有三元组中总共出现 3 次，并且每个三元组中的数字互不相同。

你需要删除其中一个三元组，并从其余每个三元组中删除一个数字。这样，你将得到 n − 1 个整数对，我们将它们视为图中的边。要求由 1 到 n 这 n 个顶点和这 n − 1 条边构成的图是连通的。请找到一种操作方案，或者报告不可能。如果有多种方案，找出被删除三元组下标最大的方案。如果仍有多种方案，输出任意一种即可。

输入格式

第一行包含一个整数 t（1 ≤ t ≤ 10⁴）——测试用例的数量。

每个测试用例的第一行包含一个整数 n（3 ≤ n ≤ 2 · 10⁵）——三元组的数量。

接下来的 n 行每行包含一个三元组，第 i 行包含 3 个整数 aᵢ、bᵢ、cᵢ（1 ≤ aᵢ、bᵢ、cᵢ ≤ n）——该三元组中的数字。保证 aᵢ ≠ bᵢ，aᵢ ≠ cᵢ，bᵢ ≠ cᵢ。

保证从 1 到 n 的每个数字恰好出现在 3 个三元组中。

保证所有测试用例的 n 之和不超过 2 · 10⁵。

输出格式

对于每个测试用例，如果无法执行所要求的操作，输出 NO。否则，第一行输出 YES。然后输出 n 行，第 i 行描述第 i 个三元组的处理结果。

如果删除了第 i 个三元组，输出 -1 -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

输出格式 1

YES
2 3
9 8
8 7
5 1
6 9
3 5
2 6
4 1
-1 -1
NO