Busy Beaver はファーマーズマーケットにいます！そこには $1$ から $N$ まで番号が振られた $N$ 個のストール（売店）があります。また、ストール間には $M$ 本の有向パスが存在します。$i$ 番目のパスはストール $a_i$ からストール $b_i$ へ向かいます（ただし $a_i \neq b_i$）。ストール $N$ から出るパスは存在せず、ストール $N$ 以外のすべてのストールからは少なくとも $1$ 本のパスが出ており、同じ始点と終点を持つパスは存在せず、ストール $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 は買い物を始めるストールを 1 つ選びます。まず、Busy Beaver は開始ストールから出る任意のパスを通って移動します。その後、毎分、Busy Beaver がパス $p$ を通って $a_p$ から $b_p$ へ移動した直後であると仮定すると、彼は以下の 2 つの行動をとります。

1. $b_p$ に到達し、$x_{b_p}$ を $1$ 増やす。
2. $x_{b_p}$ がある正の整数 $K$ の倍数である場合、Busy Beaver は次にパス $s_p$ を通る。そうでない場合、Busy Beaver は $b_p$ から出る任意のパスを通る。

もし Busy Beaver がストール $N$ に到達した場合、彼はファーマーズマーケットから去ります。ファーマーズマーケットの地図が与えられたとき、Busy Beaver が永遠にマーケットにとどまることができるような、正の整数 $K$、すべての $x_i$ の初期値、および開始ストールは存在しますか？

入力

入力の最初の行には、テストケースの数 $T$ ($1 \le T \le 10^4$) が含まれます。

各テストケースの最初の行には、2 つの整数 $N$ と $M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 4 \cdot 10^5$) がスペース区切りで含まれます。これらはマーケット内のストールの総数と有向パスの数です。

続く $M$ 行の各行には、3 つの整数 $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$ を超えないことが保証されています。

出力

各テストケースについて、Busy Beaver がストール $N$ に到達することなく永遠にマーケットにとどまることができるような $K$ の値、すべての $x_i$ の初期値、および開始ストールが存在する場合、「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$ は奇数になり、パス 8 を通ってストール 1 に到達すると $x_1$ は偶数になります。これにより、Busy Beaver が（ストール $N$ につながる）パス 9 を通ることを強制されることはなくなります。

テストケース 2 のマーケットを以下に示します。Busy Beaver が永遠にマーケットにとどまることは不可能であることが示せます。