20983번 - スパイ 2 (Spy 2) 스페셜 저지다국어

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 個の情報と合致する答えが複数存在する場合は，そのうちどれを出力してもよい．

入力は以下の形式で標準入力から与えられる．

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 ≦ 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)．