問題文

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$ 点) 追加の制約はない．

入力

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

$N$ $M$ $T_1$ $T_2$ $\\cdots$ $T_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\\vdots$ $A_M$ $B_M$ $C_M$

出力

標準出力に出力せよ．

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

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