Busy Beaver đang ở chợ nông sản! Có $N$ quầy hàng, được đánh số từ 1 đến $N$. Ngoài ra còn có $M$ con đường một chiều giữa các quầy hàng. Con đường thứ $i$ đi từ quầy $a_i$ đến quầy $b_i$, trong đó $a_i \neq b_i$. Đảm bảo rằng không có con đường nào rời khỏi quầy $N$, ít nhất một con đường rời khỏi mỗi quầy khác quầy $N$, không có hai con đường nào có cùng điểm bắt đầu và điểm kết thúc, và với mọi con đường đi từ quầy $r_1 \neq N$ đến $r_2 \neq N$, tồn tại một con đường khác đi từ $r_2$ đến $r_1$. Mỗi con đường $i$ không kết thúc tại quầy $N$ đều có một con đường kế tiếp duy nhất $s_i$. Đảm bảo rằng con đường $s_i$ có thể được sử dụng sau con đường $i$. Nói cách khác, $a_{s_i} = b_i$. Mỗi quầy cũng có một bộ đếm số nguyên $x_i$.

Busy Beaver chọn một quầy để bắt đầu mua sắm. Đầu tiên, Busy Beaver đi dọc theo bất kỳ con đường nào rời khỏi quầy bắt đầu của mình. Sau đó, mỗi phút, giả sử Busy Beaver vừa đi dọc theo con đường $p$ từ $a_p$ đến $b_p$, cậu ấy thực hiện hai hành động sau:

1. Cậu ấy đến $b_p$ và tăng $x_{b_p}$ lên 1.
2. Nếu $x_{b_p}$ là bội số của một số nguyên dương $K$ nào đó, Busy Beaver sẽ đi dọc theo con đường $s_p$ tiếp theo. Nếu không, Busy Beaver đi dọc theo bất kỳ con đường nào rời khỏi $b_p$.

Nếu Busy Beaver đến quầy $N$, cậu ấy sẽ rời khỏi chợ nông sản. Cho trước bản đồ của chợ nông sản, liệu có tồn tại một số nguyên dương $K$, các giá trị nguyên ban đầu cho tất cả $x_i$, và một quầy bắt đầu cho Busy Beaver để cậu ấy có thể ở lại chợ mãi mãi không?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$) — số lượng bộ test.

Dòng đầu tiên của mỗi bộ test chứa hai số nguyên cách nhau bởi dấu cách $N$ và $M$ ($2 \le N \le 2 \cdot 10^5$, $1 \le M \le 4 \cdot 10^5$) — tổng số quầy hàng và số lượng con đường một chiều trong chợ nông sản.

Dòng thứ $i$ trong $M$ dòng tiếp theo của mỗi bộ test chứa ba số nguyên cách nhau bởi dấu cách $a_i$, $b_i$, và $s_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le s_i \le M$) — biểu thị con đường thứ $i$ đi từ quầy $a_i$ đến quầy $b_i$, và con đường kế tiếp duy nhất của nó là $s_i$. Nếu $b_i = N$, thì $s_i = -1$, biểu thị con đường đó không có con đường kế tiếp.

Đảm bảo rằng tổng $N$ trên tất cả các bộ test không vượt quá $2 \cdot 10^5$ và tổng $M$ trên tất cả các bộ test không vượt quá $4 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ test, nếu tồn tại một giá trị $K$, các giá trị ban đầu cho tất cả $x_i$, và một quầy bắt đầu sao cho Busy Beaver có thể ở lại chợ mãi mãi mà không bao giờ đến quầy $N$, hãy in ra "YES". Nếu không, in ra "NO".

Bạn có thể in câu trả lời ở bất kỳ định dạng chữ hoa hay chữ thường nào. Ví dụ, các chuỗi "yEs", "yes", "Yes", và "YES" đều được công nhận là phản hồi khẳng định.

Ví dụ

Ví dụ 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

Ví dụ 2

YES
NO

Ghi chú

Chợ cho bộ test 1 được hiển thị dưới đây. Các quầy được khoanh tròn và các con đường có màu xanh lam. Busy Beaver có thể ở lại chợ mãi mãi. Một giải pháp là đặt $K = 2$, $x = [0, 0, 0, 0, 0]$, và ban đầu đặt Busy Beaver tại quầy 1. Busy Beaver sau đó sẽ đi dọc theo con đường khép kín qua các quầy $1 \to 2 \to 3 \to 1 \to 4 \to 1$, lặp lại mãi mãi. Khi Busy Beaver đến quầy 1 với con đường 5, $x_1$ trở thành số lẻ, và khi Busy Beaver đến quầy 1 với con đường 8, $x_1$ trở thành số chẵn. Điều này đảm bảo rằng Busy Beaver không bao giờ bị buộc phải đi theo con đường 9 (dẫn đến quầy $N$).

Chợ cho bộ test 2 được hiển thị dưới đây. Có thể thấy rằng Busy Beaver không thể ở lại chợ mãi mãi.