Busy Beaver está en el mercado de agricultores. Hay $N$ puestos, numerados del 1 al $N$. También hay $M$ caminos dirigidos entre los puestos. El $i$-ésimo camino va del puesto $a_i$ al puesto $b_i$, donde $a_i \neq b_i$. Se garantiza que ningún camino sale del puesto $N$, que al menos un camino sale de cada puesto distinto del puesto $N$, que no hay dos caminos con los mismos puestos de inicio y fin, y que para cada camino que va del puesto $r_1 \neq N$ al $r_2 \neq N$, existe otro camino que va de $r_2$ a $r_1$. Cada camino $i$ que no termina en el puesto $N$ tiene un camino sucesor único $s_i$. Se garantiza que el camino $s_i$ puede utilizarse después del camino $i$. En otras palabras, $a_{s_i} = b_i$. Cada puesto también tiene un contador entero $x_i$.

Busy Beaver elige un puesto para comenzar sus compras. Primero, Busy Beaver viaja a lo largo de cualquier camino que salga de su puesto inicial. Luego, cada minuto, suponiendo que Busy Beaver acaba de viajar a lo largo del camino $p$ desde $a_p$ hasta $b_p$, realiza las siguientes dos acciones:

1. Llega a $b_p$ e incrementa $x_{b_p}$ en 1.
2. Si $x_{b_p}$ es un múltiplo de algún entero positivo $K$, Busy Beaver tomará el camino $s_p$ a continuación. De lo contrario, Busy Beaver viaja a lo largo de cualquier camino que salga de $b_p$.

Si Busy Beaver llega alguna vez al puesto $N$, abandonará el mercado de agricultores. Dado el mapa del mercado de agricultores, ¿existe un entero positivo $K$, valores enteros iniciales para todos los $x_i$ y un puesto inicial para Busy Beaver, de modo que pueda permanecer en el mercado para siempre?

Entrada

La primera línea contiene un único entero $T$ ($1 \leq T \leq 10^4$) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros separados por espacios $N$ y $M$ ($2 \leq N \leq 2 \cdot 10^5$, $1 \leq M \leq 4 \cdot 10^5$) — el número total de puestos y el número de caminos dirigidos en el mercado de agricultores.

La $i$-ésima de las siguientes $M$ líneas de cada caso de prueba contiene tres enteros separados por espacios $a_i$, $b_i$ y $s_i$ ($1 \leq a_i, b_i \leq N$, $a_i \neq b_i$, $1 \leq s_i \leq M$) — indicando que el $i$-ésimo camino va del puesto $a_i$ al puesto $b_i$, y su camino sucesor único es $s_i$. Si $b_i = N$, entonces $s_i = -1$, indicando que el camino no tiene sucesor.

Se garantiza que la suma de $N$ sobre todos los casos de prueba no excede $2 \cdot 10^5$ y la suma de $M$ sobre todos los casos de prueba no excede $4 \cdot 10^5$.

Salida

Para cada caso de prueba, si existe un valor para $K$, valores iniciales para todos los $x_i$ y un puesto inicial tal que Busy Beaver pueda permanecer en el mercado para siempre sin llegar nunca al puesto $N$, imprima "YES". De lo contrario, imprima "NO".

Puede imprimir la respuesta en cualquier formato (mayúsculas o minúsculas). Por ejemplo, las cadenas "yEs", "yes", "Yes" y "YES" serán reconocidas como respuestas positivas.

Ejemplos

Entrada 1

2
5 9
1 2 3
2 1 7
2 3 5
3 2 2
3 1 9
1 3 4
1 4 8
4 1 1
1 5 -1
4 9
1 2 8
2 1 7
2 3 9
3 2 8
3 1 7
1 3 9
1 4 -1
2 4 -1
3 4 -1

Salida 1

YES
NO

Nota

El mercado para el caso de prueba 1 se muestra a continuación. Los puestos están rodeados y los caminos están en azul. Es posible que Busy Beaver permanezca en el mercado para siempre. Una solución es establecer $K = 2$, $x = [0, 0, 0, 0, 0]$, y colocar inicialmente a Busy Beaver en el puesto 1. Busy Beaver viajará entonces a lo largo del camino cerrado a través de los puestos $1 \to 2 \to 3 \to 1 \to 4 \to 1$, repitiéndose para siempre. Cuando Busy Beaver llega al puesto 1 con el camino 5, $x_1$ se vuelve impar, y cuando Busy Beaver llega al puesto 1 con el camino 8, $x_1$ se vuelve par. Esto asegura que Busy Beaver nunca sea forzado a tomar el camino 9 (que conduce al puesto $N$).

Diagrama 1

El mercado para el caso de prueba 2 se muestra a continuación. Se puede demostrar que es imposible que Busy Beaver permanezca en el mercado para siempre.

Diagrama 2