染色图

题目描述

Y 同学正在研究一种特殊的图构造问题。

给定一张包含 $N$ 个节点的图，你需要为每个节点染上黑色或白色。在此基础上，你可以添加任意数量的边权为 $1$ 的有向边，但必须满足一个核心约束：

• 对于图中的每一条边 $u \to v$，节点 $u$ 的颜色必须与节点 $v$ 的颜色不同。

现在有 $M$ 条限制条件，第 $i$ 条限制由三元组 $(a_i, b_i, c_i)$ 给定，要求在构造出的图中，必须存在一条从节点 $a_i$ 到节点 $b_i$ 的路径，且该路径的长度恰好为 $c_i$。注意，路径可以重复经过节点或边。

你的任务是判断是否存在一种染色方案和连边方案，能够同时满足上述所有构造约束和 $M$ 条路径限制。

输入格式

第一行输入一个整数 $T$，表示数据的组数。

对于每组数据： 第一行包含两个整数 $N$ 和 $M$，分别表示节点数量和限制条件的数量。 接下来 $M$ 行，每行包含三个整数 $a_i, b_i, c_i$，描述一条限制条件。

输出格式

对于每组数据，输出一行一个字符串。如果存在满足条件的图，输出 Yes；否则输出 No。

样例

样例输入 #1

1
5 4
1 3 4
4 2 7
4 4 0
5 2 1

样例输出 #1

Yes

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10$
• $1 \le N \le 10^6$
• $0 \le M \le 10^6$
• $1 \le a_i, b_i \le N$
• $0 \le c_i \le 10^9$