Cho biểu thức 2-CNF gồm \(N\) biến và \(M\) mệnh đề. Hãy tìm phép gán thỏa mãn có số biến nhận giá trị true (1) là nhiều nhất.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và M (\(1 \le N \le 10^5, 1 \le M \le 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i, b_i\) (\(-N \le a_i, b_i \le N, a_i \neq 0, b_i \neq 0\)).

Định dạng đầu ra

• Nếu không có phép gán, in ra NO.
• Nếu có, in ra YES ở dòng đầu, dòng thứ hai in \(N\) số 0 hoặc 1 là phép gán có nhiều biến true nhất.

Ví dụ

Input:

3 2
1 -2
2 -3

Output:

YES
1 1 0

Ràng buộc & Subtasks