P11640 Graph

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

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.

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 $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.

**[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