Se te dan $n$ ternas de enteros entre $1$ y $n$. Se garantiza que cada número aparece en total $3$ veces en todas las ternas y que los números de cada terna son distintos.
Debes eliminar una de las ternas y, de cada una de las ternas restantes, eliminar un número. Como resultado, tendrás $n-1$ pares de enteros, que consideraremos aristas de un grafo. Se requiere que el grafo con $n$ vértices numerados del $1$ al $n$ y estas $n-1$ aristas sea conexo. Encuentra una forma de hacerlo o indica que es imposible. Si hay varias formas, encuentra una que maximice el índice de la terna eliminada. Si aún hay varias formas, puedes encontrar cualquiera de ellas.
Entrada
La primera línea contiene un único entero $t$ ($1 \le t \le 10^4$): el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero $n$ ($3 \le n \le 2\cdot 10^5$): el número de ternas.
Las siguientes $n$ líneas contienen las ternas; la línea $i$ contiene $3$ enteros $a_i,b_i,c_i$ ($1 \le a_i,b_i,c_i \le n$): los números de una terna. Se garantiza que $a_i\ne b_i$, $a_i\ne c_i$ y $b_i\ne c_i$.
Se garantiza que cada número del $1$ al $n$ está incluido en exactamente $3$ ternas.
Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $2\cdot 10^5$.
Salida
Para cada caso de prueba, imprime NO si es imposible realizar las operaciones requeridas. En caso contrario, imprime YES en la primera línea. Después, imprime $n$ líneas. En la línea $i$ de estas líneas, describe el resultado de la terna $i$.
Si se elimina la terna $i$, imprime -1 -1. En caso contrario, imprime dos enteros: los dos números que quedan en esta terna después de eliminar un número de ella, en cualquier orden. Si hay varias respuestas válidas, imprime una con el máximo índice posible de la terna eliminada. Si aún hay varias respuestas válidas, puedes imprimir cualquiera de ellas.
Ejemplos
Entrada 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
Salida 1
YES 2 3 9 8 8 7 5 1 6 9 3 5 2 6 4 1 -1 -1 NO