給定一個包含 $N$ 個節點與 $M$ 條邊的有向圖 $G$，其中每條邊都有一個 $[0, 9]$ 之間的整數權重。請檢查是否存在一條從節點 1 出發的無限長路徑，使得若將路徑上的邊權視為小數的位數，該數會收斂為一個無理數。（形式上，若第 $i$ 條邊的權重為 $d_i$，則條件為 $0.d_1d_2d_3 \dots$ 是一個無理數。）

該圖可能包含自環、節點之間的多條邊，且可能是不連通的。

輸入格式

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

每組測試資料的第一行包含兩個整數 $N, M$ ($1 \le N, M \le 2 \cdot 10^5$)，分別代表圖 $G$ 中的節點數與邊數。

接下來 $M$ 行中的第 $i$ 行包含三個整數 $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$)，表示一條從 $a_i$ 到 $b_i$ 且權重為 $d_i$ 的邊。

保證所有測試資料的 $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 出發的無限長路徑對應的數皆為 $0.\overline{123123} \dots = \frac{41}{333}$，這是一個有理數。因此，無法得到無理數。

在第二組測試資料中，所有由數字 0 和 1 組成的數皆可得到。

在第三組測試資料中，不存在從節點 1 出發的無限長路徑。