You are given $n$ triplets of integers from $1$ to $n$. It is guaranteed that each number appears in all triplets a total of $3$ times, and that all numbers in each triplet are distinct.

You need to remove one of the triplets, and from all the remaining triplets, remove one number from each. As a result, you will have $n - 1$ pairs of integers, which we will treat as an edges of a graph. It is required that the graph with $n$ vertices from $1$ to $n$ and these $n - 1$ edges is connected. Find a way to do this, or report that it is impossible. If there are multiple ways, find one that maximizes index of removed triple. If there are still multiple ways, you can find any of them.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of triplets.

Next $n$ lines contain triples, $i$-th line contains $3$ integers $a_i, b_i, c_i$ ($1 \le a_i, b_i, c_i \le n$) — the numbers in a triple. It is guaranteed that $a_i \ne b_i$, $a_i \ne c_i$, $b_i \ne c_i$.

It is guaranteed that every number from $1$ to $n$ is included in exactly $3$ triples.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, print NO if it is impossible to perform the required operations. Otherwise, print YES in the first line. Then print $n$ lines. In the $i$-th of these lines, describe the result for the $i$-th triplet.

If the $i$-th triplet is removed, print -1 -1. Otherwise, print two integers: the two numbers left in this triplet after removing one number from it in any order. If there are several valid answers, output one with the maximum possible index of the removed triplet. If there are still several valid answers, you may output any of them.

Examples

Input 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

Output 1

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