Đề bài

Tại vương quốc IOI có $N$ nghị sĩ, được đánh số từ $1$ đến $N$. Là một bộ trưởng của vương quốc JOI, bạn đang cố gắng tìm ra những điệp viên trà trộn trong các nghị sĩ. Đối với mỗi nghị sĩ $i$ ($1 \le i \le N$), bạn thu thập được thông tin như sau:

• Khi $T_{i} = 1$, nghị sĩ $i$ là điệp viên.
• Khi $T_{i} = 2$, nghị sĩ $i$ không phải là điệp viên.
• Khi $T_{i} = 3$, chưa rõ nghị sĩ $i$ có phải là điệp viên hay không.

Hơn nữa, kết quả của cuộc điều tra thẩm vấn giúp bạn thu được thêm $M$ thông tin mới. Thông tin thẩm vấn thứ $j$ ($1 \le j \le M$) là việc nghị sĩ $A_{j}$ ($1 \le A_{j} \le N$) đã làm chứng rằng "nghị sĩ $B_{j}$ ($1 \le B_{j} \le N$) là điệp viên, và nghị sĩ $C_{j}$ ($1 \le C_{j} \le N$) không phải là điệp viên".

Tuy nhiên, nếu nghị sĩ $A_{j}$ là điệp viên, lời làm chứng trong thông tin thẩm vấn thứ $j$ sẽ trái với sự thật. Nghĩa là, nếu nghị sĩ $A_{j}$ là điệp viên thì ít nhất một trong hai mệnh đề "nghị sĩ $B_{j}$ là điệp viên" và "nghị sĩ $C_{j}$ không phải là điệp viên" không đúng sự thật. Mặt khác, khi nghị sĩ $A_{j}$ không phải là điệp viên, lời làm chứng trong thông tin thẩm vấn thứ $j$ có thể đúng sự thật mà cũng có thể không đúng sự thật.

Cho thông tin về từng nghị sĩ và kết quả điều tra thẩm vấn, hãy viết chương trình xác định xem $N + M$ thông tin đó có mâu thuẫn với nhau hay không, và nếu không mâu thuẫn, hãy tìm xem mỗi nghị sĩ có phải là điệp viên hay không. Nếu có nhiều đáp án phù hợp với $N + M$ thông tin, bạn có thể in ra bất kỳ đáp án nào trong số đó.

Giới hạn

• $1 \le N \le 300\,000$.
• $1 \le M \le 300\,000$.
• $1 \le T_{i} \le 3$ ($1 \le i \le N$).
• $1 \le A_{j} \le N$ ($1 \le j \le M$).
• $1 \le B_{j} \le N$ ($1 \le j \le M$).
• $1 \le C_{j} \le N$ ($1 \le j \le M$).
• $A_{j} \ne B_{j}$ ($1 \le j \le M$).
• $A_{j} \ne C_{j}$ ($1 \le j \le M$).
• $B_{j} \ne C_{j}$ ($1 \le j \le M$).

Subtask

1. ($7$ điểm) $N \le 16$, $M \le 100$.
2. ($38$ điểm) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ điểm) Không có giới hạn bổ sung.

Dữ liệu vào

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

$N$ $M$
$T_{1}$ $T_{2}$ $\dots$ $T_{N}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$:$
$A_{M}$ $B_{M}$ $C_{M}$

Dữ liệu ra

In kết quả ra đầu ra chuẩn.

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

Ngược lại, dữ liệu ra gồm $N$ dòng. Ở dòng thứ $i$ ($1 \le i \le N$), in ra $1$ nếu nghị sĩ $i$ là điệp viên, hoặc in ra $2$ nếu nghị sĩ $i$ không phải là điệp viên. Nếu có nhiều đáp án phù hợp với $N + M$ thông tin, bạn có thể in ra bất kỳ đáp án nào trong số đó.

Ví dụ

Dữ liệu vào mẫu 1

4 1
1 3 2 3
1 2 3

Dữ liệu ra mẫu 1

1
2
2
1

Trong Dữ liệu ra mẫu $1$, nghị sĩ $1$ là điệp viên, và lời làm chứng "nghị sĩ $2$ là điệp viên, và nghị sĩ $3$ không phải là điệp viên" trái với sự thật vì nghị sĩ $2$ không phải là điệp viên. Do đó, Dữ liệu ra mẫu $1$ phù hợp với các thông tin đã cho và là đáp án đúng.

Ngoài ra, đáp án trong đó chỉ có nghị sĩ $1$ là điệp viên và các nghị sĩ khác không phải là điệp viên cũng là đáp án đúng.

Dữ liệu vào mẫu 2

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

Dữ liệu ra mẫu 2

-1

Nếu giả sử nghị sĩ $3$ là điệp viên thì không phù hợp với thông tin thẩm vấn thứ $1$. Nếu giả sử nghị sĩ $3$ không phải là điệp viên thì không phù hợp với thông tin thẩm vấn thứ $2$. Vì thông tin bị mâu thuẫn nên in ra -1.

Dữ liệu vào mẫu 3

3 2
1 2 2
2 1 3
2 3 1

Dữ liệu ra mẫu 3

1
2
2

Trong Dữ liệu vào mẫu $3$, tất cả các nghị sĩ đều đã có thông tin là điệp viên hay không. Các thông tin này cũng phù hợp với thông tin thẩm vấn, do đó Dữ liệu ra mẫu $3$ là đáp án đúng duy nhất. Lưu ý rằng lời làm chứng của nghị sĩ không phải là điệp viên có thể đúng sự thật mà cũng có thể không đúng sự thật.