Busy Beaver jest na targu rolnym! Jest tam $N$ stoisk, ponumerowanych od 1 do $N$. Istnieje również $M$ skierowanych ścieżek między stoiskami. $i$-ta ścieżka prowadzi ze stoiska $a_i$ do stoiska $b_i$, gdzie $a_i \neq b_i$. Gwarantuje się, że żadna ścieżka nie wychodzi ze stoiska $N$, co najmniej jedna ścieżka wychodzi z każdego stoiska poza stoiskiem $N$, żadne dwie ścieżki nie mają tych samych stoisk początkowych i końcowych, oraz dla każdej ścieżki prowadzącej ze stoiska $r_1 \neq N$ do $r_2 \neq N$ istnieje inna ścieżka prowadząca z $r_2$ do $r_1$. Każda ścieżka $i$, która nie kończy się na stoisku $N$, ma unikalną ścieżkę następczą $s_i$. Gwarantuje się, że ścieżka $s_i$ może zostać użyta po ścieżce $i$. Innymi słowy, $a_{s_i} = b_i$. Każde stoisko posiada również licznik całkowity $x_i$.

Busy Beaver wybiera stoisko, od którego rozpoczyna zakupy. Najpierw Busy Beaver podróżuje wzdłuż dowolnej ścieżki wychodzącej z jego stoiska początkowego. Następnie, co minutę, zakładając, że Busy Beaver właśnie przebył ścieżkę $p$ z $a_p$ do $b_p$, wykonuje następujące dwie czynności:

1. Dociera do $b_p$ i zwiększa $x_{b_p}$ o 1.
2. Jeśli $x_{b_p}$ jest wielokrotnością pewnej dodatniej liczby całkowitej $K$, Busy Beaver wybierze w następnym kroku ścieżkę $s_p$. W przeciwnym razie Busy Beaver podróżuje wzdłuż dowolnej ścieżki wychodzącej z $b_p$.

Jeśli Busy Beaver kiedykolwiek dotrze do stoiska $N$, opuści targ rolny. Mając daną mapę targu, czy istnieje dodatnia liczba całkowita $K$, początkowe wartości całkowite dla wszystkich $x_i$ oraz stoisko początkowe dla Busy Beavera, takie aby mógł on pozostać na targu na zawsze?

Wejście

Pierwsza linia zawiera pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^4$) — liczbę zestawów danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $N$ i $M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 4 \cdot 10^5$) — łączną liczbę stoisk oraz liczbę skierowanych ścieżek na targu.

$i$-ta z kolejnych $M$ linii każdego zestawu danych zawiera trzy liczby całkowite $a_i$, $b_i$ oraz $s_i$ ($1 \le a_i, b_i \le N$, $a_i \neq b_i$, $1 \le s_i \le M$) — oznaczające, że $i$-ta ścieżka prowadzi ze stoiska $a_i$ do stoiska $b_i$, a jej unikalna ścieżka następcza to $s_i$. Jeśli $b_i = N$, to $s_i = -1$, co oznacza, że ścieżka nie ma następcy.

Gwarantuje się, że suma $N$ we wszystkich zestawach danych nie przekracza $2 \cdot 10^5$, a suma $M$ we wszystkich zestawach danych nie przekracza $4 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych, jeśli istnieje wartość $K$, wartości początkowe dla wszystkich $x_i$ oraz stoisko początkowe takie, że Busy Beaver może pozostać na targu na zawsze, nigdy nie docierając do stoiska $N$, wypisz „YES”. W przeciwnym razie wypisz „NO”.

Odpowiedź można wypisać w dowolnej wielkości liter. Na przykład ciągi „yEs”, „yes”, „Yes” oraz „YES” będą rozpoznawane jako odpowiedzi pozytywne.

Przykład

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

Wyjście 1

YES
NO

Uwagi

Targ dla pierwszego zestawu danych przedstawiono poniżej. Stoiska są w kółkach, a ścieżki są niebieskie. Możliwe jest, aby Busy Beaver pozostał na targu na zawsze. Rozwiązaniem jest ustawienie $K = 2$, $x = [0, 0, 0, 0, 0]$ i rozpoczęcie od stoiska 1. Busy Beaver będzie wtedy podróżował wzdłuż zamkniętej ścieżki przez stoiska $1 \to 2 \to 3 \to 1 \to 4 \to 1$, powtarzając to w nieskończoność. Kiedy Busy Beaver dociera do stoiska 1 ścieżką 5, $x_1$ staje się nieparzyste, a kiedy dociera do stoiska 1 ścieżką 8, $x_1$ staje się parzyste. Zapewnia to, że Busy Beaver nigdy nie jest zmuszony do wybrania ścieżki 9 (która prowadzi do stoiska $N$).

Targ dla drugiego zestawu danych przedstawiono poniżej. Można wykazać, że Busy Beaver nie jest w stanie pozostać na targu na zawsze.