Busy Beaver 來到農夫市集！這裡有 $N$ 個攤位，編號從 $1$ 到 $N$。攤位之間有 $M$ 條有向路徑。第 $i$ 條路徑從攤位 $a_i$ 通往攤位 $b_i$，其中 $a_i \neq b_i$。保證沒有路徑離開攤位 $N$，且除了攤位 $N$ 之外，每個攤位至少有一條路徑離開；沒有兩條路徑具有相同的起點和終點；對於每一條從攤位 $r_1 \neq N$ 通往 $r_2 \neq N$ 的路徑，都存在另一條從 $r_2$ 通往 $r_1$ 的路徑。每一條不以攤位 $N$ 為終點的路徑 $i$ 都有一個唯一的後繼路徑 $s_i$。保證路徑 $s_i$ 可以在路徑 $i$ 之後使用。換句話說，$a_{s_i} = b_i$。每個攤位還有一個整數計數器 $x_i$。

Busy Beaver 選擇一個攤位開始購物。首先，Busy Beaver 沿著離開他起始攤位的任意路徑行進。接著，每一分鐘，假設 Busy Beaver 剛沿著從 $a_p$ 到 $b_p$ 的路徑 $p$ 行進，他會執行以下兩個動作：

1. 他到達 $b_p$ 並將 $x_{b_p}$ 加 $1$。
2. 如果 $x_{b_p}$ 是某個正整數 $K$ 的倍數，Busy Beaver 下一步將沿著路徑 $s_p$ 行進。否則，Busy Beaver 沿著離開 $b_p$ 的任意路徑行進。

如果 Busy Beaver 到達了攤位 $N$，他就會離開農夫市集。給定農夫市集的地圖，是否存在一個正整數 $K$、所有 $x_i$ 的初始整數值，以及一個 Busy Beaver 的起始攤位，使得他可以永遠留在市集中？

輸入格式

第一行包含一個整數 $T$ ($1 \le T \le 10^4$)，代表測試資料的組數。

每一組測試資料的第一行包含兩個以空格分隔的整數 $N$ 和 $M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 4 \cdot 10^5$)，代表農夫市集中的攤位總數和有向路徑總數。

接下來 $M$ 行中的第 $i$ 行包含三個以空格分隔的整數 $a_i, b_i, s_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le s_i \le M$)，表示第 $i$ 條路徑從攤位 $a_i$ 通往攤位 $b_i$，其唯一的後繼路徑為 $s_i$。若 $b_i = N$，則 $s_i = -1$，表示該路徑沒有後繼路徑。

保證所有測試資料的 $N$ 之和不超過 $2 \cdot 10^5$，且所有測試資料的 $M$ 之和不超過 $4 \cdot 10^5$。

輸出格式

對於每組測試資料，如果存在一個 $K$ 值、所有 $x_i$ 的初始值以及一個起始攤位，使得 Busy Beaver 可以永遠留在市集中而不到達攤位 $N$，請輸出「YES」。否則，輸出「NO」。

你可以以任何大小寫形式輸出答案。例如，「yEs」、「yes」、「Yes」和「YES」都會被視為肯定的回應。

範例

輸入 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

輸出 1

YES
NO

說明

測試資料 1 的市集如下圖所示。攤位以圓圈表示，路徑以藍色表示。Busy Beaver 有可能永遠留在市集中。一種解法是設定 $K = 2$，$x = [0, 0, 0, 0, 0]$，並將 Busy Beaver 初始置於攤位 1。Busy Beaver 隨後將沿著經過攤位 $1 \to 2 \to 3 \to 1 \to 4 \to 1$ 的封閉路徑行進，並永遠重複。當 Busy Beaver 透過路徑 5 到達攤位 1 時，$x_1$ 變為奇數，而當 Busy Beaver 透過路徑 8 到達攤位 1 時，$x_1$ 變為偶數。這確保了 Busy Beaver 永遠不會被迫選擇路徑 9（該路徑通往攤位 $N$）。

測試資料 2 的市集如下圖所示。可以證明 Busy Beaver 不可能永遠留在市集中。