$N$ 個のノードと $M$ 本の辺を持つ有向グラフ $G$ が与えられる。各辺には $[0, 9]$ の範囲の整数重みが割り当てられている。ノード 1 から始まる無限に長い歩道（walk）が存在し、その辺の重みを小数第 $i$ 位の数字として見たとき、その数が無理数に収束するかどうかを判定せよ。（形式的には、第 $i$ 辺の重みを $d_i$ としたとき、条件は $0.d_1d_2d_3 \dots$ が無理数であることである。）

グラフは自己ループを持つことがあり、同じノードのペア間に複数の辺が存在することもあり、連結であるとは限らない。

入力

入力は以下の形式で与えられる。

$T$ $N$ $M$ $a_1$ $b_1$ $d_1$ $\vdots$ $a_M$ $b_M$ $d_M$

1 行目にはテストケースの数 $T$ ($1 \le T \le 2 \cdot 10^5$) が含まれる。 各テストケースの 1 行目には、グラフ $G$ のノード数 $N$ と辺数 $M$ ($1 \le N, M \le 2 \cdot 10^5$) が含まれる。 続く $M$ 行の各行には、ノード $a_i$ から $b_i$ への重み $d_i$ の辺を表す 3 つの整数 $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$) が含まれる。

すべてのテストケースにおける $N$ の総和および $M$ の総和は、いずれも $2 \cdot 10^5$ を超えないことが保証される。

出力

$T$ 行出力せよ。各行には Yes または No（大文字小文字は問わない）を出力すること。

小課題

• （35点）すべてのテストケースにおける $N$ の総和および $M$ の総和は、いずれも 3000 を超えない。
• （65点）追加の制約はない。

入出力例

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

出力 1

No
Yes
No

注記

1 番目のテストケースでは、ノード 1 から始まるすべての無限に長い歩道は $0.123123 \dots = \frac{41}{333}$ という有理数に対応するため、無理数を得ることはできません。

2 番目のテストケースでは、数字 0 と 1 を含むすべての数が得られます。

3 番目のテストケースでは、ノード 1 から始まる無限に長い歩道は存在しません。