On vous donne un graphe orienté $G$ avec $N$ sommets et $M$ arêtes, où chaque arête possède un poids entier dans $[0, 9]$. Vérifiez s'il existe une marche infiniment longue depuis le sommet 1 telle que, si l'on considère les poids comme les chiffres d'un nombre décimal, ce nombre converge vers un nombre irrationnel. (Formellement, si le poids de la $i^{th}$ arête est $d_i$, alors la condition est que $0.d_1d_2d_3 \dots$ est irrationnel.)

Le graphe peut comporter des boucles, contenir plusieurs arêtes entre la même paire de sommets, et être déconnecté.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 2 \cdot 10^5$), le nombre de cas de test.

La première ligne de chaque cas de test contient deux entiers $N, M$ ($1 \le N, M \le 2 \cdot 10^5$), le nombre de sommets et d'arêtes dans $G$, respectivement.

La $i^{th}$ des $M$ lignes suivantes de chaque cas de test contient trois entiers $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$), indiquant une arête allant de $a_i$ vers $b_i$ avec un poids $d_i$.

Il est garanti que la somme de $N$ sur tous les cas de test et la somme de $M$ sur tous les cas de test ne dépassent pas $2 \cdot 10^5$.

Sortie

Affichez $T$ lignes, chacune contenant soit Yes soit No (insensible à la casse).

Scoring

• (35 points) La somme de $N$ sur tous les cas de test et la somme de $M$ sur tous les cas de test ne dépassent pas 3000.
• (65 points) Aucune contrainte supplémentaire.

Note

Dans le premier cas de test, toutes les marches infiniment longues depuis le sommet 1 correspondent au nombre $0.123123 \dots = \frac{41}{333}$, qui est rationnel. Par conséquent, il n'est pas possible d'obtenir un nombre irrationnel.

Dans le deuxième cas de test, tous les nombres avec les chiffres 0 et 1 sont réalisables.

Dans le troisième cas de test, il n'existe pas de marche infiniment longue depuis le sommet 1.

Exemples

Entrée 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

Sortie 1

No
Yes
No