给定一个包含 $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{123} = \frac{41}{333}$，这是一个有理数。因此，无法得到无理数。
• 在第二个测试用例中，所有由数字 0 和 1 组成的数均可得到。
• 在第三个测试用例中，不存在从节点 1 出发的无限长路径。