$1$부터 $n$까지의 정수로 이루어진 세 수의 묶음이 $n$개 주어집니다. 각 수는 모든 세 수의 묶음에서 합쳐서 정확히 $3$번 등장하며, 각 세 수의 묶음 안의 수는 모두 서로 다름이 보장됩니다.

세 수의 묶음 하나를 제거하고, 남은 모든 세 수의 묶음에서 각각 수 하나를 제거해야 합니다. 그러면 정수 쌍 $n-1$개가 남으며, 이를 그래프의 간선으로 취급합니다. $1$부터 $n$까지의 정점을 갖는 그래프가 이 $n-1$개의 간선으로 연결되어야 합니다. 이를 수행하는 방법을 찾거나, 불가능하다고 보고하세요. 방법이 여러 개라면 제거한 세 수의 묶음의 인덱스가 최대인 방법을 찾으세요. 그래도 방법이 여러 개라면 그중 아무 것이나 찾아도 됩니다.

입력

첫 번째 줄에는 테스트 케이스의 수인 정수 $t$ ($1 \le t \le 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 세 수의 묶음의 수인 정수 $n$ ($3 \le n \le 2\cdot10^5$)이 주어집니다.

다음 $n$개의 줄에는 세 수의 묶음이 주어집니다. $i$번째 줄에는 세 수의 묶음의 수인 정수 $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\cdot10^5$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, 요구된 연산을 수행할 수 없다면 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