問題文

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

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

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

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

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

制約

• $1 \le N \le 300\,000$.
• $1 \le M \le 300\,000$.
• $1 \le T_{i} \le 3$ ($1 \le i \le N$).
• $1 \le A_{j} \le N$ ($1 \le j \le M$).
• $1 \le B_{j} \le N$ ($1 \le j \le M$).
• $1 \le C_{j} \le N$ ($1 \le j \le M$).
• $A_{j} \ne B_{j}$ ($1 \le j \le M$).
• $A_{j} \ne C_{j}$ ($1 \le j \le M$).
• $B_{j} \ne C_{j}$ ($1 \le j \le M$).

小課題

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

入力

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

$N$ $M$
$T_{1}$ $T_{2}$ $\dots$ $T_{N}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$:$
$A_{M}$ $B_{M}$ $C_{M}$

出力

標準出力に出力せよ．

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

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