001 - スパイ 2

時間制限 2 秒 / メモリ制限 1024 MB / 得点 100 / x 0 /

TLE
2sec
MLE
1024MB
得点
100

問題文

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

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

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

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

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

制約

  • 1 ≦ N ≦ 300 000．
  • 1 ≦ M ≦ 300 000．
  • 1 ≦ Ti ≦ 3 (1 ≦ i ≦ N)．
  • 1 ≦ Aj ≦ N (1 ≦ j ≦ M)．
  • 1 ≦ Bj ≦ N (1 ≦ j ≦ M)．
  • 1 ≦ Cj ≦ N (1 ≦ j ≦ M)．
  • Aj ≠ Bj (1 ≦ j ≦ M)．
  • Aj ≠ Cj (1 ≦ j ≦ M)．
  • Bj ≠ Cj (1 ≦ j ≦ M)．

小課題

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

入力

入力は以下の形式で標準入力から与えられる．
N M
T1 T2 … TN
A1 B1 C1
A2 B2 C2
:
AM BM CM

出力

標準出力に出力せよ．

与えられた情報が矛盾している場合，-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 が唯一の正解となる．スパイでない議員の証言は，事実であるかもしれないし，そうでないかもしれないことに注意せよ．