第20回日本情報オリンピック　二次予選

2020年12月14日
情報オリンピック日本委員会

問題文

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

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

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

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

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

制約

• 1 ≦ N ≦ 300 000．
• 1 ≦ M ≦ 300 000．
• 1 ≦ T_i ≦ 3 (1 ≦ i ≦ N)．
• 1 ≦ A_j ≦ N (1 ≦ j ≦ M)．
• 1 ≦ B_j ≦ N (1 ≦ j ≦ M)．
• 1 ≦ C_j ≦ N (1 ≦ j ≦ M)．
• A_j ≠ B_j (1 ≦ j ≦ M)．
• A_j ≠ C_j (1 ≦ j ≦ M)．
• B_j ≠ C_j (1 ≦ j ≦ M)．

小課題

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

入力

入力は以下の形式で標準入力から与えられる．
N M
T₁ T₂ … T_N
A₁ B₁ C₁
A₂ B₂ C₂
:
A_M B_M C_M

出力

標準出力に出力せよ．

与えられた情報が矛盾している場合，-1 を 1 行で出力せよ．

そうでない場合，出力は N 行からなる．i 行目 (1 ≦ i ≦ N) には議員 i がスパイである場合 1 を，議員 i がスパイでない場合 2 を出力せよ．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 が唯一の正解となる．スパイでない議員の証言は，事実であるかもしれないし，そうでないかもしれないことに注意せよ．