Busy Beaver находится на фермерском рынке! На рынке есть $N$ прилавков, пронумерованных от 1 до $N$. Также между прилавками есть $M$ направленных путей. $i$-й путь ведет от прилавка $a_i$ к прилавку $b_i$, где $a_i \neq b_i$. Гарантируется, что из прилавка $N$ не выходит ни один путь, из каждого прилавка, кроме $N$, выходит хотя бы один путь, никакие два пути не имеют одинаковые начальный и конечный прилавки, и для каждого пути из прилавка $r_1 \neq N$ в $r_2 \neq N$ существует другой путь из $r_2$ в $r_1$. У каждого пути $i$, который не заканчивается в прилавке $N$, есть уникальный путь-преемник $s_i$. Гарантируется, что путь $s_i$ можно использовать после пути $i$. Другими словами, $a_{s_i} = b_i$. У каждого прилавка также есть целочисленный счетчик $x_i$.

Busy Beaver выбирает прилавок, чтобы начать свои покупки. Сначала Busy Beaver проходит по любому пути, выходящему из его начального прилавка. Затем каждую минуту, предполагая, что Busy Beaver только что прошел по пути $p$ из $a_p$ в $b_p$, он выполняет следующие два действия:

1. Он достигает $b_p$ и увеличивает $x_{b_p}$ на 1.
2. Если $x_{b_p}$ кратно некоторому положительному целому числу $K$, Busy Beaver следующим пойдет по пути $s_p$. В противном случае Busy Beaver проходит по любому пути, выходящему из $b_p$.

Если Busy Beaver когда-нибудь достигнет прилавка $N$, он покинет фермерский рынок. Учитывая карту фермерского рынка, существуют ли положительное целое число $K$, начальные целочисленные значения для всех $x_i$ и начальный прилавок для Busy Beaver такие, чтобы он мог оставаться на рынке вечно?

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

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

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

$i$-я из следующих $M$ строк каждого тестового случая содержит три целых числа $a_i$, $b_i$ и $s_i$ ($1 \le a_i, b_i \le N$, $a_i \neq b_i$, $1 \le s_i \le M$) — указывающих, что $i$-й путь ведет от прилавка $a_i$ к прилавку $b_i$, а его уникальный путь-преемник — $s_i$. Если $b_i = N$, то $s_i = -1$, что означает, что у пути нет преемника.

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

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

Для каждого тестового случая, если существуют значение $K$, начальные значения для всех $x_i$ и начальный прилавок такие, что Busy Beaver может оставаться на рынке вечно, никогда не достигая прилавка $N$, выведите «YES». В противном случае выведите «NO».

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные ответы.

Примеры

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

2
5 9
1 2 3
2 1 7
2 3 5
3 2 2
3 1 9
1 3 4
1 4 8
4 1 1
1 5 -1
4 9
1 2 8
2 1 7
2 3 9
3 2 8
3 1 7
1 3 9
1 4 -1
2 4 -1
3 4 -1

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

YES
NO

Примечание

Рынок для первого тестового случая показан ниже. Прилавки обведены кружками, а пути обозначены синим цветом. Busy Beaver может оставаться на рынке вечно. Одно из решений — установить $K = 2$, $x = [0, 0, 0, 0, 0]$ и изначально поместить Busy Beaver в прилавок 1. Тогда Busy Beaver будет бесконечно повторять замкнутый путь через прилавки $1 \to 2 \to 3 \to 1 \to 4 \to 1$. Когда Busy Beaver достигает прилавка 1 по пути 5, $x_1$ становится нечетным, а когда Busy Beaver достигает прилавка 1 по пути 8, $x_1$ становится четным. Это гарантирует, что Busy Beaver никогда не будет вынужден выбрать путь 9 (который ведет к прилавку $N$).

Рынок для второго тестового случая показан ниже. Можно показать, что Busy Beaver не может оставаться на рынке вечно.