Dany jest skierowany graf $G$ o $N$ wierzchołkach i $M$ krawędziach, gdzie każda krawędź ma wagę całkowitą z przedziału $[0, 9]$. Sprawdź, czy istnieje nieskończenie długa ścieżka wychodząca z wierzchołka 1, taka że jeśli potraktujemy wagi krawędzi jako cyfry liczby dziesiętnej, to liczba ta będzie liczbą niewymierną. (Formalnie: jeśli waga $i$-tej krawędzi wynosi $d_i$, to warunkiem jest, aby $0.d_1d_2d_3 \dots$ było liczbą niewymierną).

Graf może zawierać pętle własne, wiele krawędzi między tą samą parą wierzchołków oraz może być niespójny.

Wejście

Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \le T \le 2 \cdot 10^5$), liczbę zestawów danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $N, M$ ($1 \le N, M \le 2 \cdot 10^5$), odpowiednio liczbę wierzchołków i krawędzi w grafie $G$.

$i$-ta z kolejnych $M$ linii każdego zestawu danych zawiera trzy liczby całkowite $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$), oznaczające krawędź z $a_i$ do $b_i$ o wadze $d_i$.

Gwarantuje się, że suma $N$ po wszystkich zestawach danych oraz suma $M$ po wszystkich zestawach danych nie przekraczają $2 \cdot 10^5$.

Wyjście

Wypisz $T$ linii, z których każda zawiera słowo Yes lub No (wielkość liter nie ma znaczenia).

Podzadania

• (35 punktów) Suma $N$ po wszystkich zestawach danych oraz suma $M$ po wszystkich zestawach danych nie przekraczają 3000.
• (65 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

No
Yes
No

Uwagi

W pierwszym zestawie danych wszystkie nieskończenie długie ścieżki z wierzchołka 1 odpowiadają liczbie $0.\overline{123123} \dots = \frac{41}{333}$, która jest wymierna. Dlatego nie jest możliwe uzyskanie liczby niewymiernej.

W drugim zestawie danych możliwe jest uzyskanie wszystkich liczb składających się z cyfr 0 i 1.

W trzecim zestawie danych nie istnieje nieskończenie długa ścieżka wychodząca z wierzchołka 1.