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$ 变为奇数；当通过路径 $8$ 到达摊位 $1$ 时，$x_1$ 变为偶数。这确保了 Busy Beaver 永远不会被迫选择路径 $9$（该路径通向摊位 $N$）。

测试用例 2 的市场结构如下图所示。可以证明 Busy Beaver 不可能永远留在市场中。