Busy Beaver est au marché des fermiers ! Il y a $N$ stands, numérotés de 1 à $N$. Il existe également $M$ chemins dirigés entre les stands. Le $i$-ième chemin va du stand $a_i$ au stand $b_i$, où $a_i \neq b_i$. Il est garanti qu'aucun chemin ne quitte le stand $N$, qu'au moins un chemin quitte chaque stand autre que le stand $N$, qu'aucun couple de chemins n'a les mêmes stands de départ et d'arrivée, et que pour chaque chemin allant du stand $r_1 \neq N$ au stand $r_2 \neq N$, il existe un autre chemin allant de $r_2$ à $r_1$. Chaque chemin $i$ qui ne se termine pas au stand $N$ possède un chemin successeur unique $s_i$. Il est garanti que le chemin $s_i$ peut être utilisé après le chemin $i$. En d'autres termes, $a_{s_i} = b_i$. Chaque stand possède également un compteur entier $x_i$.

Busy Beaver choisit un stand pour commencer ses achats. D'abord, Busy Beaver parcourt n'importe quel chemin quittant son stand de départ. Ensuite, chaque minute, en supposant que Busy Beaver vient de parcourir le chemin $p$ de $a_p$ à $b_p$, il effectue les deux actions suivantes :

1. Il atteint $b_p$ et incrémente $x_{b_p}$ de 1.
2. Si $x_{b_p}$ est un multiple d'un entier positif $K$, Busy Beaver empruntera ensuite le chemin $s_p$. Sinon, Busy Beaver parcourt n'importe quel chemin quittant $b_p$.

Si Busy Beaver atteint un jour le stand $N$, il quittera le marché des fermiers. Étant donné la carte du marché des fermiers, existe-t-il un entier positif $K$, des valeurs entières initiales pour tous les $x_i$, et un stand de départ pour Busy Beaver, tels qu'il puisse rester au marché pour toujours ?

Entrée

La première ligne contient un seul entier $T$ ($1 \le T \le 10^4$) — le nombre de cas de test.

La première ligne de chaque cas de test contient deux entiers séparés par un espace $N$ et $M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 4 \cdot 10^5$) — le nombre total de stands et le nombre de chemins dirigés dans le marché des fermiers.

La $i$-ième des $M$ lignes suivantes de chaque cas de test contient trois entiers séparés par un espace $a_i$, $b_i$, et $s_i$ ($1 \le a_i, b_i \le N$, $a_i \neq b_i$, $1 \le s_i \le M$) — indiquant que le $i$-ième chemin va du stand $a_i$ au stand $b_i$, et que son chemin successeur unique est $s_i$. Si $b_i = N$, alors $s_i = -1$, indiquant que le chemin n'a pas de successeur.

Il est garanti que la somme de $N$ sur tous les cas de test n'excède pas $2 \cdot 10^5$ et que la somme de $M$ sur tous les cas de test n'excède pas $4 \cdot 10^5$.

Sortie

Pour chaque cas de test, s'il existe une valeur pour $K$, des valeurs initiales pour tous les $x_i$, et un stand de départ tels que Busy Beaver puisse rester au marché pour toujours sans jamais atteindre le stand $N$, affichez « YES ». Sinon, affichez « NO ».

Vous pouvez afficher la réponse en majuscules ou en minuscules. Par exemple, les chaînes « yEs », « yes », « Yes » et « YES » seront reconnues comme des réponses positives.

Exemples

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

Sortie 1

YES
NO

Remarque

Le marché pour le premier cas de test est illustré ci-dessous. Les stands sont entourés et les chemins sont en bleu. Il est possible pour Busy Beaver de rester au marché pour toujours. Une solution consiste à définir $K = 2$, $x = [0, 0, 0, 0, 0]$, et à placer initialement Busy Beaver au stand 1. Busy Beaver parcourra alors le chemin fermé à travers les stands $1 \to 2 \to 3 \to 1 \to 4 \to 1$, en répétant indéfiniment. Lorsque Busy Beaver atteint le stand 1 avec le chemin 5, $x_1$ devient impair, et lorsque Busy Beaver atteint le stand 1 avec le chemin 8, $x_1$ devient pair. Cela garantit que Busy Beaver n'est jamais forcé d'emprunter le chemin 9 (qui mène au stand $N$).

Figure 1. Le marché pour le premier cas de test.

Le deuxième cas de test est illustré ci-dessous. Il est impossible d'éviter le stand $N$ indéfiniment.

Figure 2. Le marché pour le deuxième cas de test.