Busy Beaver đang cố gắng để vào MIT. Thay vì làm bài thi SAT, cậu ấy nghĩ rằng mình có thể làm tốt hơn — tốt hơn gấp ba lần, khi cậu ấy bắt tay vào giải 3-SAT! Cậu ấy đã tìm ra một lời giải thực sự tuyệt vời, nhưng không may là lề trang giấy trong đơn ứng tuyển của cậu ấy quá hẹp để chứa nó. Vì vậy, cậu ấy đã tự nghĩ ra phiên bản bài toán của riêng mình, nhưng cậu ấy cần sự giúp đỡ của bạn để giải nó:

Cho $n, m$ là các số nguyên dương. Có $n$ biến $x_1, \dots, x_n$ nhận giá trị trong $\{0, 1\}$. Một mệnh đề là tích của ba biến $x_a \cdot x_b \cdot x_c$ với các chỉ số $1 \le a \le b \le c \le n$. Bạn được cho một biểu thức là tổng của $m$ mệnh đề như vậy. Ví dụ, một biểu thức như thế với bốn biến và ba mệnh đề có thể là:

$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4.$$

Hãy xác định xem có thể chọn các giá trị $x_1, \dots, x_n$ sao cho biểu thức kết quả là số lẻ hay không.

Dữ liệu vào

Mỗi tệp chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 10^5$).

Mô tả các bộ dữ liệu như sau:

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 10^5$).

$m$ dòng tiếp theo của mỗi bộ dữ liệu mô tả từng mệnh đề trong tổng. Dòng thứ $i$ gồm ba số nguyên cách nhau bởi dấu cách $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$), biểu thị rằng mệnh đề thứ $i$ của tổng là $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$.

Đảm bảo rằng tổng của $n$ và tổng của $m$ trên tất cả các bộ dữ liệu không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa chuỗi YES nếu tồn tại cách thiết lập các $x_i$ để biểu thức là số lẻ, và NO trong trường hợp ngược lại. Bạn có thể in mỗi chữ cái ở bất kỳ định dạng chữ hoa hay chữ thường nào. Ví dụ, yes, Yes, YeS đều sẽ được công nhận là câu trả lời khẳng định.

Sau đó, nếu bạn trả lời YES, hãy in dòng thứ hai gồm các số nguyên cách nhau bởi dấu cách $x_1, \dots, x_n$ ($x_i = 0$ hoặc $1$) làm cho biểu thức có giá trị là một số lẻ. Nếu có nhiều lời giải khả thi, hãy in bất kỳ lời giải nào trong số đó.

Nhiệm vụ con

Bạn sẽ nhận được 50% số điểm cho mỗi nhiệm vụ con nếu các phản hồi YES/NO là chính xác, nhưng các giá trị $x_i$ được cung cấp thì không. Với mỗi bộ dữ liệu, bạn phải xuất ra chính xác $n$ giá trị của $x_i$ để nhận điểm một phần.

• (50 điểm): Trong mỗi mệnh đề, không có biến nào xuất hiện nhiều hơn một lần, tức là $a_i < b_i < c_i$.
• (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

2
4 3
1 2 3
1 3 4
2 3 4
3 2
1 2 3
1 2 3

Dữ liệu ra 1

YES
1 1 1 1
NO

Ghi chú

Bộ dữ liệu đầu tiên giống hệt với ví dụ trong mô tả bài toán. Trong biểu thức này, việc thiết lập tất cả các biến bằng 1 làm cho biểu thức bằng $1 + 1 + 1 = 3$, là một số lẻ.

Trong bộ dữ liệu thứ hai, biểu thức được cho là $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$. Có thể chứng minh rằng không có cách thiết lập nào của $x_1, x_2, x_3$ làm cho biểu thức này là số lẻ.