E. Irrational Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph $$$G$$$ with $$$N$$$ nodes and $$$M$$$ edges, where each edge has an integer weight in $$$[0,9]$$$. Check if there exists an infinitely long walk from node $$$1$$$ where, if we view the weights as the digits of a decimal number, this number converges to an irrational number. (Formally, if the weight of the $$$i^\text{th}$$$ edge is $$$d_i$$$, then the condition is that $$$0.\overline{d_1 d_2 d_3 \dots}$$$ is irrational.)

The graph can have self loops, contain multiple edges between the same pair of nodes, and be disconnected.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$), the number of test cases.

The first line of each test case contains two integers $$$N, M$$$ ($$$1 \le N, M \le 2 \cdot 10^5$$$), the number of nodes and edges in $$$G$$$, respectively.

The $$$i^\text{th}$$$ of the next $$$M$$$ lines of each test case contains three integers $$$a_i, b_i, d_i$$$ ($$$1 \le a_i, b_i \le N$$$, $$$0 \le d_i \le 9$$$), indicating an edge from $$$a_i$$$ to $$$b_i$$$ with weight $$$d_i$$$.

It is guaranteed that the sum of $$$N$$$ over all test cases and the sum of $$$M$$$ over all test cases both do not exceed $$$2 \cdot 10^5$$$.

Output

Output $$$T$$$ lines, each containing either Yes or No (case insensitive).

Scoring
  • (35 points) The sum of $$$N$$$ over all test cases and the sum of $$$M$$$ over all test cases both do not exceed $$$3000$$$.
  • (65 points) No additional constraints.
Example
Input
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
Output
No
Yes
No
Note

In the first test case, all infinitely long walks from node $$$1$$$ correspond to the number $$$0.\overline{123123\dots} = \frac{41}{333}$$$, which is rational. Therefore, it's not possible to obtain an irrational number.

In the second test case, all numbers with digits $$$0$$$ and $$$1$$$ are obtainable.

In the third test case, there does not exist an infinitely long walk from node $$$1$$$.