スパイ 2 (Spy 2)

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

JOI 2021 · JCIOI · CC BY-SA 4.0