Background

Hack testdata has been added in Subtask #5 and is not scored.

Problem Description

There is a graph with $n$ vertices. Each vertex can be black or white.

There are $m$ constraints. The $i$-th constraint gives $a_i, b_i, c_i$, meaning that from $a_i$ to $b_i$ there must exist a path of length $c_i$. The path may pass through an edge or a vertex multiple times.

Determine whether there exists a directed graph whose edges all have weight $1$, such that:

• All the above $m$ constraints are satisfied.
• If the graph has $k$ edges, then for every $\forall 1 \le i \le k$, let the $i$-th edge be directed from $u_i$ to $v_i$. Then the colors of $u_i$ and $v_i$ are different.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains two integers $n, m$.

The next $m$ lines each contain three integers $a_i, b_i, c_i$.

Output Format

Output $T$ lines. Each line contains a string $s \in \{\tt{Yes}, \tt{No}\}$.

The $i$-th line is the answer to the $i$-th test case.

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

Yes

Hint

[Sample Explanation]

You can construct

to satisfy the requirements.

[Constraints]

This problem uses bundled tests.

• Subtask #1 ($5\text{pts}$): $m = 0$.
• Subtask #2 ($20\text{pts}$): $n \le 10$.
• Subtask #3 ($25\text{pts}$): $n \le 10^3$.
• Subtask #4 ($50\text{pts}$): no special constraints.

For $100\%$ of the data, $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$.

Translated by ChatGPT 5