問題文

JOI 国には N 人の議員がおり，1 から N までの番号がつけられている．JOI 国の大臣であるあなたは，議員の中にいるスパイを探し出そうとしている．あなたは各議員 i (1 \leqq i \leqq N) について次のような情報を得た．

• T_i = 1 のとき，議員 i はスパイである．
• T_i = 2 のとき，議員 i はスパイではない．
• T_i = 3 のとき，議員 i がスパイであるかどうかは不明である．

更に聞き取り調査を行った結果，新たに M 個の情報を得ることができた．j 番目の聞き取り調査の情報 (1 \leqq j \leqq M) は，議員 A_j (1 \leqq A_j \leqq N) が「議員 B_j (1 \leqq B_j \leqq N) はスパイであり，かつ議員 C_j (1 \leqq C_j \leqq N) はスパイでない」と証言したというものである．

ただし，議員 A_j がスパイであれば，j 番目の聞き取り調査の情報における証言は事実とは異なる．すなわち，もし議員 A_j がスパイであれば，「議員 B_j はスパイである」「議員 C_j はスパイでない」のうち，少なくとも一方は事実ではない．一方で，議員 A_j がスパイでないとき，j 番目の聞き取り調査の情報における証言は事実かもしれないし，そうでないかもしれない．

各議員の情報と，聞き取り調査の結果が与えられるので，それら N + M 個の情報が矛盾しているかを判定し，矛盾していないなら，それぞれの議員がスパイかどうかを求めるプログラムを作成せよ．N + M 個の情報と合致する答えが複数存在する場合は，そのうちどれを出力してもよい．

制約

• 1 \leqq N \leqq 300\,000．
• 1 \leqq M \leqq 300\,000．
• 1 \leqq T_i \leqq 3 (1 \leqq i \leqq N)．
• 1 \leqq A_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq B_j \leqq N (1 \leqq j \leqq M)．
• 1 \leqq C_j \leqq N (1 \leqq j \leqq M)．
• A_j \neq B_j (1 \leqq j \leqq M)．
• A_j \neq C_j (1 \leqq j \leqq M)．
• B_j \neq C_j (1 \leqq j \leqq M)．

小課題

1. (7 点) N \leqq 16，M \leqq 100．
2. (38 点) N \leqq 3\,000，M \leqq 3\,000．
3. (55 点) 追加の制約はない．

入力例 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 が唯一の正解となる．スパイでない議員の証言は，事実であるかもしれないし，そうでないかもしれないことに注意せよ．