Deskripsi Masalah

Di Negara JOI terdapat $N$ orang anggota parlemen yang diberi nomor dari $1$ sampai $N$. Sebagai seorang menteri di Negara JOI, Anda sedang berusaha menemukan mata-mata di antara para anggota parlemen. Untuk setiap anggota parlemen $i$ ($1 \le i \le N$), Anda memperoleh informasi sebagai berikut:

• Ketika $T_{i} = 1$, anggota parlemen $i$ adalah mata-mata.
• Ketika $T_{i} = 2$, anggota parlemen $i$ bukan mata-mata.
• Ketika $T_{i} = 3$, tidak diketahui apakah anggota parlemen $i$ adalah mata-mata atau bukan.

Lebih lanjut, sebagai hasil dari penyelidikan wawancara, Anda memperoleh $M$ informasi baru. Informasi wawancara ke-$j$ ($1 \le j \le M$) adalah bahwa anggota parlemen $A_{j}$ ($1 \le A_{j} \le N$) bersaksi bahwa "anggota parlemen $B_{j}$ ($1 \le B_{j} \le N$) adalah mata-mata, dan anggota parlemen $C_{j}$ ($1 \le C_{j} \le N$) bukan mata-mata".

Namun, jika anggota parlemen $A_{j}$ adalah mata-mata, maka kesaksian dalam informasi wawancara ke-$j$ bertentangan dengan fakta. Dengan kata lain, jika anggota parlemen $A_{j}$ adalah mata-mata, setidaknya salah satu dari "anggota parlemen $B_{j}$ adalah mata-mata" dan "anggota parlemen $C_{j}$ bukan mata-mata" tidaklah benar. Di sisi lain, ketika anggota parlemen $A_{j}$ bukan mata-mata, kesaksian dalam informasi wawancara ke-$j$ bisa jadi benar, dan bisa jadi tidak benar.

Diberikan informasi mengenai setiap anggota parlemen serta hasil wawancara, buatlah program untuk menentukan apakah $N + M$ informasi tersebut saling bertentangan, dan jika tidak bertentangan, tentukan apakah masing-masing anggota parlemen adalah mata-mata atau bukan. Jika terdapat beberapa jawaban yang sesuai dengan $N + M$ informasi tersebut, Anda boleh mencetak yang mana saja di antaranya.

Batasan

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

Subsoal

1. ($7$ poin) $N \le 16$, $M \le 100$.
2. ($38$ poin) $N \le 3\,000$, $M \le 3\,000$.
3. ($55$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dari masukan standar dalam format berikut:

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

Keluaran

Cetak ke keluaran standar.

Jika informasi yang diberikan saling bertentangan, cetak -1 dalam $1$ baris.

Jika tidak, keluaran terdiri dari $N$ baris. Pada baris ke-$i$ ($1 \le i \le N$), cetak $1$ jika anggota parlemen $i$ adalah mata-mata, atau cetak $2$ jika anggota parlemen $i$ bukan mata-mata. Jika terdapat beberapa jawaban yang sesuai dengan $N + M$ informasi tersebut, Anda boleh mencetak yang mana saja di antaranya.

Contoh Masukan dan Keluaran

Contoh Masukan 1

4 1
1 3 2 3
1 2 3

Contoh Keluaran 1

1
2
2
1

Pada Contoh Keluaran $1$, anggota parlemen $1$ adalah mata-mata, dan kesaksian bahwa "anggota parlemen $2$ adalah mata-mata, dan anggota parlemen $3$ bukan mata-mata" bertentangan dengan fakta karena anggota parlemen $2$ bukan mata-mata. Oleh karena itu, Contoh Keluaran $1$ sesuai dengan informasi yang diberikan dan merupakan jawaban yang benar.

Selain ini, jawaban bahwa hanya anggota parlemen $1$ yang merupakan mata-mata sedangkan anggota parlemen lainnya bukan mata-mata juga merupakan jawaban yang benar.

Contoh Masukan 2

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

Contoh Keluaran 2

-1

Jika anggota parlemen $3$ adalah mata-mata, hal ini tidak sesuai dengan informasi wawancara ke-$1$. Jika anggota parlemen $3$ bukan mata-mata, hal ini tidak sesuai dengan informasi wawancara ke-$2$. Karena informasinya saling bertentangan, cetak -1.

Contoh Masukan 3

3 2
1 2 2
2 1 3
2 3 1

Contoh Keluaran 3

1
2
2

Pada Contoh Masukan $3$, informasi apakah setiap anggota parlemen merupakan mata-mata atau bukan telah diberikan untuk semua anggota parlemen. Karena informasi ini juga sesuai dengan informasi wawancara, maka Contoh Keluaran $3$ adalah satu-satunya jawaban yang benar. Perhatikan bahwa kesaksian dari anggota parlemen yang bukan mata-mata bisa jadi benar, dan bisa jadi tidak benar.