โจทย์ปัญหา

ในประเทศ JOI มีสมาชิกรัฐสภา $N$ คน ซึ่งมีหมายเลขกำกับตั้งแต่ $1$ ถึง $N$ คุณซึ่งเป็นรัฐมนตรีของประเทศ JOI กำลังพยายามค้นหาสายลับที่แฝงตัวอยู่ในหมู่สมาชิกรัฐสภา สำหรับสมาชิกรัฐสภาแต่ละคน $i$ ($1 \le i \le N$) คุณได้รับข้อมูลดังต่อไปนี้:

• เมื่อ $T_{i} = 1$ สมาชิกรัฐสภา $i$ เป็นสายลับ
• เมื่อ $T_{i} = 2$ สมาชิกรัฐสภา $i$ ไม่เป็นสายลับ
• เมื่อ $T_{i} = 3$ ยังไม่ทราบว่าสมาชิกรัฐสภา $i$ เป็นสายลับหรือไม่

นอกจากนี้ จากผลการสอบปากคำเพิ่มเติม ทำให้คุณได้รับข้อมูลใหม่อีก $M$ ข้อ ข้อมูลจากการสอบปากคำข้อที่ $j$ ($1 \le j \le M$) คือ สมาชิกรัฐสภา $A_{j}$ ($1 \le A_{j} \le N$) ได้ให้การว่า "สมาชิกรัฐสภา $B_{j}$ ($1 \le B_{j} \le N$) เป็นสายลับ และสมาชิกรัฐสภา $C_{j}$ ($1 \le C_{j} \le N$) ไม่เป็นสายลับ"

ทว่า หากสมาชิกรัฐสภา $A_{j}$ เป็นสายลับ คำให้การในข้อมูลจากการสอบปากคำข้อที่ $j$ จะขัดแย้งกับความเป็นจริง กล่าวคือ หากสมาชิกรัฐสภา $A_{j}$ เป็นสายลับ อย่างน้อยหนึ่งอย่างระหว่าง "สมาชิกรัฐสภา $B_{j}$ เป็นสายลับ" และ "สมาชิกรัฐสภา $C_{j}$ ไม่เป็นสายลับ" จะไม่เป็นความจริง ในทางกลับกัน เมื่อสมาชิกรัฐสภา $A_{j}$ ไม่เป็นสายลับ คำให้การในข้อมูลจากการสอบปากคำข้อที่ $j$ อาจจะเป็นความจริงหรือไม่เป็นความจริงก็ได้

เมื่อกำหนดข้อมูลของสมาชิกรัฐสภาแต่ละคนและผลการสอบปากคำ จงเขียนโปรแกรมเพื่อตรวจสอบว่าข้อมูลทั้ง $N + M$ ข้อนั้นขัดแย้งกันเองหรือไม่ และหากไม่ขัดแย้ง จงหาว่าสมาชิกรัฐสภาแต่ละคนเป็นสายลับหรือไม่ หากมีคำตอบที่สอดคล้องกับข้อมูลทั้ง $N + M$ ข้ออยู่หลายคำตอบ สามารถพิมพ์คำตอบใดก็ได้

ข้อจำกัด

• $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$).

งานย่อย

1. ($7$ คะแนน) $N \le 16$, $M \le 100$.
2. ($38$ คะแนน) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ข้อมูลนำเข้า

ข้อมูลนำเข้าจะถูกกำหนดให้จากข้อมูลนำเข้ามาตรฐานในรูปแบบต่อไปนี้:

$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}$

ข้อมูลส่งออก

พิมพ์ผลลัพธ์ลงในข้อมูลส่งออกมาตรฐาน

หากข้อมูลที่กำหนดให้มีความขัดแย้งกัน จงพิมพ์ -1 ใน $1$ บรรทัด

มิฉะนั้น ข้อมูลส่งออกจะประกอบด้วย $N$ บรรทัด ในบรรทัดที่ $i$ ($1 \le i \le N$) ให้พิมพ์ $1$ หากสมาชิกรัฐสภา $i$ เป็นสายลับ หรือพิมพ์ $2$ หากสมาชิกรัฐสภา $i$ ไม่เป็นสายลับ หากมีคำตอบที่สอดคล้องกับข้อมูลทั้ง $N + M$ ข้ออยู่หลายคำตอบ สามารถพิมพ์คำตอบใดก็ได้

ตัวอย่างข้อมูลนำเข้าและส่งออก

ตัวอย่างข้อมูลนำเข้า 1

4 1
1 3 2 3
1 2 3

ตัวอย่างข้อมูลส่งออก 1

1
2
2
1

ในตัวอย่างข้อมูลส่งออก $1$ สมาชิกรัฐสภา $1$ เป็นสายลับ และคำให้การที่ว่า "สมาชิกรัฐสภา $2$ เป็นสายลับ และสมาชิกรัฐสภา $3$ ไม่เป็นสายลับ" ขัดแย้งกับความเป็นจริงเนื่องจากสมาชิกรัฐสภา $2$ ไม่เป็นสายลับ ดังนั้น ตัวอย่างข้อมูลส่งออก $1$ จึงสอดคล้องกับข้อมูลที่กำหนดให้และเป็นคำตอบที่ถูกต้อง

นอกจากนี้ คำตอบที่มีเพียงสมาชิกรัฐสภา $1$ เท่านั้นที่เป็นสายลับ และสมาชิกรัฐสภาคนอื่นไม่เป็นสายลับ ก็เป็นคำตอบที่ถูกต้องเช่นกัน

ตัวอย่างข้อมูลนำเข้า 2

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

ตัวอย่างข้อมูลส่งออก 2

-1

หากสมมติว่าสมาชิกรัฐสภา $3$ เป็นสายลับ จะไม่สอดคล้องกับข้อมูลจากการสอบปากคำข้อที่ $1$ หากสมมติว่าสมาชิกรัฐสภา $3$ ไม่เป็นสายลับ จะไม่สอดคล้องกับข้อมูลจากการสอบปากคำข้อที่ $2$ เนื่องจากข้อมูลขัดแย้งกัน จึงพิมพ์ -1

ตัวอย่างข้อมูลนำเข้า 3

3 2
1 2 2
2 1 3
2 3 1

ตัวอย่างข้อมูลส่งออก 3

1
2
2

ในตัวอย่างข้อมูลนำเข้า $3$ สมาชิกรัฐสภาทุกคนมีข้อมูลระบุชัดเจนว่าเป็นสายลับหรือไม่ ซึ่งข้อมูลเหล่านี้สอดคล้องกับข้อมูลจากการสอบปากคำด้วย ดังนั้น ตัวอย่างข้อมูลส่งออก $3$ จึงเป็นคำตอบที่ถูกต้องเพียงคำตอบเดียว โปรดสังเกตว่าคำให้การของสมาชิกรัฐสภาที่ไม่เป็นสายลับอาจจะเป็นความจริงหรือไม่เป็นความจริงก็ได้