$N$개의 노드와 $M$개의 간선으로 이루어진 유향 그래프 $G$가 주어지며, 각 간선은 $[0, 9]$ 범위의 정수 가중치를 가집니다. 노드 1에서 시작하는 무한히 긴 경로가 존재하여, 경로상의 간선 가중치를 소수점 아래의 자릿수로 보았을 때 이 수가 무리수로 수렴하는지 확인하십시오. (형식적으로, $i$번째 간선의 가중치가 $d_i$라면, $0.d_1d_2d_3\dots$가 무리수여야 한다는 조건입니다.)

그래프는 자기 루프를 가질 수 있고, 같은 두 노드 사이에 여러 간선이 존재할 수 있으며, 연결되어 있지 않을 수도 있습니다.

입력

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 2 \cdot 10^5$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 그래프 $G$의 노드 수와 간선 수를 나타내는 두 정수 $N, M$ ($1 \le N, M \le 2 \cdot 10^5$)이 주어집니다.

다음 $M$개의 줄에는 각 간선에 대한 정보가 주어지며, $i$번째 줄에는 $a_i$에서 $b_i$로 향하는 가중치 $d_i$인 간선을 나타내는 세 정수 $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$)가 주어집니다.

모든 테스트 케이스에 대해 $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{123123\dots} = \frac{41}{333}$이라는 수에 대응되며, 이는 유리수입니다. 따라서 무리수를 얻는 것은 불가능합니다.

두 번째 테스트 케이스에서, 숫자 0과 1로 이루어진 모든 수를 얻을 수 있습니다.

세 번째 테스트 케이스에서, 노드 1에서 시작하는 무한히 긴 경로는 존재하지 않습니다.