Bạn được cho một đồ thị có hướng $G$ với $N$ đỉnh và $M$ cạnh, trong đó mỗi cạnh có trọng số nguyên nằm trong đoạn $[0, 9]$. Hãy kiểm tra xem có tồn tại một đường đi vô hạn bắt đầu từ đỉnh 1 sao cho nếu ta coi các trọng số là các chữ số của một số thập phân, thì số này là một số vô tỉ hay không. (Nói một cách hình thức, nếu trọng số của cạnh thứ $i$ là $d_i$, thì điều kiện là $0.d_1d_2d_3 \dots$ là số vô tỉ.)

Đồ thị có thể có khuyên, nhiều cạnh nối giữa cùng một cặp đỉnh, và có thể không liên thông.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 2 \cdot 10^5$), số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $N, M$ ($1 \le N, M \le 2 \cdot 10^5$), lần lượt là số lượng đỉnh và số lượng cạnh trong $G$.

$M$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i, b_i, d_i$ ($1 \le a_i, b_i \le N, 0 \le d_i \le 9$), biểu thị một cạnh từ $a_i$ đến $b_i$ với trọng số $d_i$.

Đảm bảo rằng tổng $N$ trên tất cả các bộ dữ liệu và tổng $M$ trên tất cả các bộ dữ liệu đều không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng chứa hoặc Yes hoặc No (không phân biệt chữ hoa chữ thường).

Nhiệm vụ con

• (35 điểm) Tổng $N$ trên tất cả các bộ dữ liệu và tổng $M$ trên tất cả các bộ dữ liệu đều không vượt quá 3000.
• (65 điểm) Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

No
Yes
No

Ghi chú

Trong bộ dữ liệu đầu tiên, tất cả các đường đi vô hạn từ đỉnh 1 đều tương ứng với số $0.\overline{123} = \frac{41}{333}$, là một số hữu tỉ. Do đó, không thể thu được một số vô tỉ.

Trong bộ dữ liệu thứ hai, tất cả các số với các chữ số 0 và 1 đều có thể thu được.

Trong bộ dữ liệu thứ ba, không tồn tại đường đi vô hạn bắt đầu từ đỉnh 1.