Дан ориентированный граф $G$ с $N$ вершинами и $M$ ребрами, где каждое ребро имеет целочисленный вес в диапазоне $[0, 9]$. Проверьте, существует ли бесконечно длинный путь из вершины 1, такой что, если рассматривать веса ребер как цифры десятичной дроби, это число сходится к иррациональному числу. (Формально, если вес $i$-го ребра равен $d_i$, то условие заключается в том, что $0.d_1d_2d_3 \dots$ является иррациональным числом.)

Граф может содержать петли, кратные ребра между одной и той же парой вершин, а также может быть несвязным.

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 2 \cdot 10^5$), количество тестовых случаев.

Первая строка каждого тестового случая содержит два целых числа $N, M$ ($1 \le N, M \le 2 \cdot 10^5$), количество вершин и ребер в $G$ соответственно.

$i$-я из следующих $M$ строк каждого тестового случая содержит три целых числа $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$), обозначающих ребро из $a_i$ в $b_i$ с весом $d_i$.

Гарантируется, что сумма $N$ по всем тестовым случаям и сумма $M$ по всем тестовым случаям не превышают $2 \cdot 10^5$.

Выходные данные

Выведите $T$ строк, каждая из которых содержит либо Yes или No (регистр не имеет значения).

Оценка

• (35 баллов) Сумма $N$ по всем тестовым случаям и сумма $M$ по всем тестовым случаям не превышают 3000.
• (65 баллов) Дополнительные ограничения отсутствуют.

Примеры

Входные данные 1

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

Выходные данные 1

No
Yes
No

Примечание

В первом тестовом случае все бесконечно длинные пути из вершины 1 соответствуют числу $0.\overline{123} = \frac{41}{333}$, которое является рациональным. Следовательно, получить иррациональное число невозможно.

Во втором тестовом случае достижимы все числа, состоящие из цифр 0 и 1.

В третьем тестовом случае не существует бесконечно длинного пути из вершины 1.