Busy Beaver는 농산물 직거래 장터에 있습니다! 장터에는 $1$부터 $N$까지 번호가 매겨진 $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$으로 가는 다른 경로가 존재함이 보장됩니다. 가판대 $N$에서 끝나지 않는 각 경로 $i$에는 고유한 후속 경로 $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$에 도달하면 장터를 떠나게 됩니다. 장터의 지도가 주어졌을 때, Busy Beaver가 장터에 영원히 머물 수 있도록 하는 양의 정수 $K$, 모든 $x_i$의 초기 정수 값, 그리고 시작 가판대가 존재하는지 판별하십시오.

입력

첫 번째 줄에는 테스트 케이스의 수 $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$)이 공백으로 구분되어 주어집니다.

다음 $M$개의 줄 중 $i$번째 줄에는 세 개의 정수 $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$를 넘지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, Busy Beaver가 가판대 $N$에 도달하지 않고 장터에 영원히 머물 수 있는 $K$, 모든 $x_i$의 초기값, 그리고 시작 가판대가 존재한다면 "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

참고

테스트 케이스 1의 장터는 아래와 같습니다. 가판대는 원으로 표시되어 있고 경로는 파란색으로 표시되어 있습니다. 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가 경로 5를 통해 가판대 1에 도착하면 $x_1$은 홀수가 되고, 경로 8을 통해 가판대 1에 도착하면 $x_1$은 짝수가 됩니다. 이는 Busy Beaver가 가판대 $N$으로 이어지는 경로 9를 선택하도록 강제되지 않음을 보장합니다.

테스트 케이스 2의 장터는 아래와 같습니다. Busy Beaver가 장터에 영원히 머무는 것은 불가능함을 보일 수 있습니다.