AT_arc188_c [ARC188C] Honest or Liar or Confused

[problemUrl]: https://atcoder.jp/contests/arc188/tasks/arc188_c $ 1 $ から $ N $ までの番号がついた $ N $ 人の村人が住む村があります。 各村人は、正直者であるか嘘つきであるかのどちらかです。また、村人のうち何人かは混乱しています。 あなたは、村人による証言を $ M $ 個手に入れました。この証言は、$ i=1,2,\ \ldots\ ,M $ に対して $ A_i,\ B_i,\ C_i $ で与えられ、 - $ C_i=0 $ であれば、村人 $ A_i $ が村人 $ B_i $ を正直者であると証言したこと - $ C_i=1 $ であれば、村人 $ A_i $ が村人 $ B_i $ を嘘つきであると証言したこと を表します。 全ての村人は、他の全ての村人について正直者と嘘つきのどちらであるかを知っており、あなたに対して次のような規則で証言を行ったことが分かっています。 - 混乱していない正直者は必ず正しい証言をする。 - 混乱していない嘘つきは必ず嘘の証言をする。 - 混乱している正直者は必ず嘘の証言をする。 - 混乱している嘘つきは必ず正しい証言をする。 すなわち、混乱していなければ正直者は正しい証言を、嘘つきは嘘の証言をしますが、混乱していると逆になります。 あなたは**混乱している村人の組**を予想することにしました。 混乱している村人の組を決めると、与えられた $ M $ 個の証言からなる証言の組が「矛盾する」かどうかが定まります。 ここで、証言の組が「矛盾する」というのは、各村人が正直者であるか嘘つきであるかをどのように決めても、証言の組の中に、村人が行う証言の規則に反するものが存在することを意味します。 与えられた証言の組が矛盾しないような**混乱している村人の組**を $ 1 $ つ見つけてください。 ただし、どのような村人の組が混乱しているとしても与えられた証言の組が矛盾する場合は、そのことを指摘してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

与えられた証言の組が矛盾しないような混乱している村人の組が存在するとき、混乱している村人の組を表す長さ $ N $ の文字列を出力せよ。このとき出力される文字列では、村人 $ i $ が混乱している場合 $ i $ 文字目が `1`、そうでない場合 $ i $ 文字目が `0` であるようにせよ。 そのような混乱している村人の組が存在しないとき、`-1` と出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ M\ \leq\ \mathrm{min}\ \lbrace\ 2\ \times\ 10^5,N(N-1)\ \rbrace $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N,\ A_i\ \neq\ B_i $ - $ i\neq\ j $ のとき $ A_i\neq\ A_j $ または $ B_i\neq\ B_j $ - $ C_i=0 $ または $ C_i=1 $ - 入力される値はすべて整数である ### Sample Explanation 1 村人 $ 1 $ が混乱していない正直者、村人 $ 2 $ が混乱している嘘つき、村人 $ 3 $ が混乱していない正直者であると仮定します。 このとき、村人 $ 1 $ は、村人 $ 2 $ が嘘つきである、村人 $ 3 $ が正直者であると正しい証言をします。 また、村人 $ 2 $ は嘘つきですが混乱しているため、村人 $ 3 $ が正直者であると正しい証言をします。 したがって、与えられた証言が全て村人の証言の規則通りに得られるため、村人 $ 2 $ のみ混乱していることを表す `010` は正当な出力の $ 1 $ つです。 ### Sample Explanation 2 村人 $ 2,3 $ が混乱していると仮定してみます。 このとき、各村人が正直者であるかどうかについて $ 2^3=8 $ 通りの組み合わせがあります。 このうち、例えば、「村人 $ 1 $ が（混乱していない）正直者、村人 $ 2 $ が（混乱している）嘘つき、村人 $ 3 $ が（混乱している）正直者」であるとすると、村人 $ 2 $ は規則によれば正しい証言をするはずですが、村人 $ 1 $ を嘘つきであると嘘の証言をしています。 他の組み合わせに対しても、同様に規則に反する証言が生じることを確認できます。 したがって、村人 $ 2,3 $ が混乱しているとすると、与えられた証言の組は矛盾します。 実は、このケースでは、どのような村人の組が混乱しているとしても与えられた証言の組は矛盾します。 ### Sample Explanation 3 混乱している人数は任意であり、題意の条件が満たされるならば $ 0 $ 人や全員でもよいです。