Nước JOI có \(N\) nghị sĩ, được đánh số từ \(1\) đến \(N\). Là một bộ trưởng, bạn đang cố tìm ra những gián điệp trong số các nghị sĩ. Với mỗi nghị sĩ \(i\) (\(1 \le i \le N\)), bạn có thông tin sau:

• Nếu \(T_i=1\), nghị sĩ \(i\) là gián điệp.
• Nếu \(T_i=2\), nghị sĩ \(i\) không phải gián điệp.
• Nếu \(T_i=3\), chưa biết nghị sĩ \(i\) có phải gián điệp hay không.

Qua phỏng vấn, bạn thu được thêm \(M\) thông tin. Thông tin thứ \(j\) (\(1 \le j \le M\)) cho biết nghị sĩ \(A_j\) đã phát biểu: “Nghị sĩ \(B_j\) là gián điệp, đồng thời nghị sĩ \(C_j\) không phải gián điệp.”

Nếu nghị sĩ \(A_j\) là gián điệp thì phát biểu này không đúng sự thật. Cụ thể, ít nhất một trong hai mệnh đề “nghị sĩ \(B_j\) là gián điệp” và “nghị sĩ \(C_j\) không phải gián điệp” phải sai. Ngược lại, nếu nghị sĩ \(A_j\) không phải gián điệp thì phát biểu của người đó có thể đúng hoặc sai.

Cho thông tin về từng nghị sĩ và kết quả phỏng vấn, hãy viết chương trình xác định \(N+M\) thông tin có mâu thuẫn với nhau hay không. Nếu không mâu thuẫn, hãy xác định một cách gán trạng thái gián điệp hoặc không phải gián điệp cho từng nghị sĩ sao cho phù hợp với tất cả thông tin. Nếu có nhiều đáp án phù hợp, có thể in ra bất kỳ đáp án nào.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, M\).

Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \ldots, T_N\).

Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j, B_j, C_j\). Các số trên cùng một dòng được cách nhau bởi dấu cách.

Dữ liệu ra

Nếu các thông tin đã cho mâu thuẫn với nhau, in ra -1 trên một dòng.

Ngược lại, in ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa \(1\) nếu nghị sĩ \(i\) là gián điệp, hoặc \(2\) nếu nghị sĩ \(i\) không phải gián điệp. Nếu có nhiều đáp án phù hợp với toàn bộ \(N+M\) thông tin, có thể in ra bất kỳ đáp án nào.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le M \le 300\,000\).
• \(1 \le T_i \le 3\) với mọi \(1 \le i \le N\).
• \(1 \le A_j \le N\) với mọi \(1 \le j \le M\).
• \(1 \le B_j \le N\) với mọi \(1 \le j \le M\).
• \(1 \le C_j \le N\) với mọi \(1 \le j \le M\).
• \(A_j \ne B_j\) với mọi \(1 \le j \le M\).
• \(A_j \ne C_j\) với mọi \(1 \le j \le M\).
• \(B_j \ne C_j\) với mọi \(1 \le j \le M\).

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

1. (7 điểm) \(N \le 16\), \(M \le 100\).
2. (38 điểm) \(N \le 3000\), \(M \le 3000\).
3. (55 điểm) Không có ràng buộc bổ sung.

Ví dụ

4 1
1 3 2 3
1 2 3

1
2
2
1

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

-1

3 2
1 2 2
2 1 3
2 3 1

1
2
2

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.