$1$ から $n$ までの整数からなる $n$ 個の三つ組が与えられます。各整数はすべての三つ組を通じて合計 $3$ 回現れ、各三つ組に含まれる整数は互いに異なることが保証されます。

三つ組を $1$ 個削除し、残ったすべての三つ組からそれぞれ整数を $1$ 個削除する必要があります。その結果、$n-1$ 個の整数の組が得られ、これらをグラフの辺とみなします。$1$ から $n$ までの $n$ 個の頂点とこれらの $n-1$ 本の辺からなるグラフが連結でなければなりません。このようにする方法を求めるか、不可能であると報告してください。方法が複数ある場合は、削除する三つ組の番号が最大になるものを求めてください。それでも方法が複数ある場合は、どれを求めてもかまいません。

入力

最初の行には、テストケース数を表す整数 $t$ ($1 \le t \le 10^4$) が $1$ 個与えられます。

各テストケースの最初の行には、三つ組の個数を表す整数 $n$ ($3 \le n \le 2 \cdot 10^5$) が $1$ 個与えられます。

続く $n$ 行には三つ組が与えられます。$i$ 行目には、三つ組の整数である $3$ 個の整数 $a_i,b_i,c_i$ ($1 \le a_i,b_i,c_i \le n$) が与えられます。$a_i \ne b_i$、$a_i \ne c_i$、$b_i \ne c_i$ が保証されます。

$1$ から $n$ までの各整数が、ちょうど $3$ 個の三つ組に含まれることが保証されます。

すべてのテストケースにわたる $n$ の総和は $2 \cdot 10^5$ 以下であることが保証されます。

出力

各テストケースについて、要求された操作を行うことが不可能なら NO を出力してください。可能なら、最初の行に YES を出力してください。その後、$n$ 行を出力してください。これらのうち $i$ 行目には、$i$ 番目の三つ組に対する結果を記述してください。

$i$ 番目の三つ組を削除する場合は、-1 -1 を出力してください。それ以外の場合は、三つ組から整数を $1$ 個削除した後に残る $2$ 個の整数を任意の順序で出力してください。有効な答えが複数ある場合は、削除する三つ組の番号が最大になるものを出力してください。それでも有効な答えが複数ある場合は、どれを出力してもかまいません。

入出力例

入力 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