AT_joi2021_yo2_e スパイ 2 (Spy 2)

[problemUrl]: https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_e 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 $ 個の情報と合致する答えが複数存在する場合は，そのうちどれを出力してもよい．

入力は以下の形式で標準入力から与えられる． > $ 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\ \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 $ 点) 追加の制約はない． ### Sample Explanation 1 出力例 $ 1 $ において議員 $ 1 $ はスパイであり，「議員 $ 2 $ はスパイであり，かつ議員 $ 3 $ はスパイでない」という証言は議員 $ 2 $ がスパイでないため事実と異なる．したがって，出力例 $ 1 $ は与えられた情報に合致しており，正解となる． この他に，議員 $ 1 $ のみがスパイであり，他の議員はスパイではない，という答えも正解となる． ### Sample Explanation 2 議員 $ 3 $ がスパイであるとすると，$ 1 $ 番目の聞き取り調査の情報と合致しない．議員 $ 3 $ がスパイでないとすると，$ 2 $ 番目の聞き取り調査の情報と合致しない．情報が矛盾しているため，`-1` を出力する． ### Sample Explanation 3 入力例 $ 3 $ において，すべての議員はスパイかそうでないかの情報が与えられている．これらは聞き取り調査の情報とも合致しているため，出力例 $ 3 $ が唯一の正解となる．スパイでない議員の証言は，事実であるかもしれないし，そうでないかもしれないことに注意せよ．