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.