Se te da un grafo dirigido $G$ con $N$ nodos y $M$ aristas, donde cada arista tiene un peso entero en $[0, 9]$. Comprueba si existe un camino infinitamente largo desde el nodo 1 donde, si vemos los pesos como los dígitos de un número decimal, este número converge a un número irracional. (Formalmente, si el peso de la $i$-ésima arista es $d_i$, entonces la condición es que $0.d_1d_2d_3 \dots$ sea irracional).

El grafo puede tener bucles propios, contener múltiples aristas entre el mismo par de nodos y estar desconectado.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 2 \cdot 10^5$), el número de casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $N, M$ ($1 \le N, M \le 2 \cdot 10^5$), el número de nodos y aristas en $G$, respectivamente.

La $i$-ésima de las siguientes $M$ líneas de cada caso de prueba contiene tres enteros $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$), indicando una arista desde $a_i$ hacia $b_i$ con peso $d_i$.

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

Salida

Imprime $T$ líneas, cada una conteniendo ya sea Yes o No (sin distinguir entre mayúsculas y minúsculas).

Subtareas

• (35 puntos) La suma de $N$ sobre todos los casos de prueba y la suma de $M$ sobre todos los casos de prueba no exceden 3000.
• (65 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

3
4 4
1 2 1
1 2 1
2 3 2
3 1 3
2 4
1 1 0
1 2 1
2 1 1
2 2 0
6 6
1 2 4
1 3 5
2 4 6
2 5 7
6 6 8
6 6 9

Salida 1

No
Yes
No

Nota

En el primer caso de prueba, todos los caminos infinitamente largos desde el nodo 1 corresponden al número $0.\overline{123123 \dots} = \frac{41}{333}$, el cual es racional. Por lo tanto, no es posible obtener un número irracional.

En el segundo caso de prueba, todos los números con dígitos 0 y 1 son obtenibles.

En el tercer caso de prueba, no existe un camino infinitamente largo desde el nodo 1.