C - Honest or Liar or Confused Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

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 つ見つけてください。 ただし、どのような村人の組が混乱しているとしても与えられた証言の組が矛盾する場合は、そのことを指摘してください。

制約

  • 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
  • 入力される値はすべて整数である

入力

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

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 と出力せよ。

入力例 1

3 3
1 2 1
1 3 0
2 3 0

出力例 1

010

村人 1 が混乱していない正直者、村人 2 が混乱している嘘つき、村人 3 が混乱していない正直者であると仮定します。

このとき、村人 1 は、村人 2 が嘘つきである、村人 3 が正直者であると正しい証言をします。 また、村人 2 は嘘つきですが混乱しているため、村人 3 が正直者であると正しい証言をします。

したがって、与えられた証言が全て村人の証言の規則通りに得られるため、村人 2 のみ混乱していることを表す 010 は正当な出力の 1 つです。

入力例 2

3 6
1 2 1
1 3 0
2 1 1
2 3 0
3 1 1
3 2 0

出力例 2

-1

村人 2,3 が混乱していると仮定してみます。

このとき、各村人が正直者であるかどうかについて 2^3=8 通りの組み合わせがあります。 このうち、例えば、「村人 1 が（混乱していない）正直者、村人 2 が（混乱している）嘘つき、村人 3 が（混乱している）正直者」であるとすると、村人 2 は規則によれば正しい証言をするはずですが、村人 1 を嘘つきであると嘘の証言をしています。 他の組み合わせに対しても、同様に規則に反する証言が生じることを確認できます。

したがって、村人 2,3 が混乱しているとすると、与えられた証言の組は矛盾します。

実は、このケースでは、どのような村人の組が混乱しているとしても与えられた証言の組は矛盾します。

入力例 3

3 0

出力例 3

000

混乱している人数は任意であり、題意の条件が満たされるならば 0 人や全員でもよいです。

Score : 700 points

Problem Statement

There is a village with N villagers numbered from 1 to N. Each villager is honest or a liar. Additionally, some villagers are confused.

You have obtained M testimonies from the villagers. Each testimony is given by A_i, B_i, C_i for i=1,2,\ldots,M, representing:

  • If C_i=0, villager A_i testified that villager B_i is honest.
  • If C_i=1, villager A_i testified that villager B_i is a liar.

All villagers know whether every other villager is honest or a liar, and you know that they made their testimonies to you according to the following rules:

  • An honest villager who is not confused always tells the truth.
  • A liar who is not confused always tells lies.
  • A confused honest villager always tells lies.
  • A confused liar always tells the truth.

In other words, if they are not confused, honest villagers always tell the truth, and liars always tell lies, but if they are confused, it is reversed.

You have decided to guess the set of villagers who are confused. Given a choice of villagers who are confused, whether the set of testimonies "contradicts" or not is determined. Here, a set of testimonies is said to contradict if, no matter how you assign honest or liar statuses to the villagers, there is at least one testimony that violates the villagers' testimony rules.

Find a set of confused villagers such that the given set of testimonies does not contradict. If no such set of confused villagers exists, indicate that fact.

Constraints

  • 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
  • A_i \neq A_j or B_i \neq B_j for i \neq j.
  • C_i = 0 or 1.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

Output

If there exists a set of confused villagers such that the given set of testimonies does not contradict, print a string of length N representing the set of confused villagers. In this string, the i-th character should be 1 if villager i is confused, and 0 otherwise.

If no such set of confused villagers exists, print -1.

Sample Input 1

3 3
1 2 1
1 3 0
2 3 0

Sample Output 1

010

Suppose villager 1 is an honest villager who is not confused, villager 2 is a confused liar, and villager 3 is an honest villager who is not confused.

In this case, villager 1 correctly testifies that villager 2 is a liar and villager 3 is honest. Also, villager 2, who is a liar but confused, tells the truth and testifies that villager 3 is honest.

Therefore, all given testimonies are consistent with the villagers' testimony rules, so 010, indicating that only villager 2 is confused, is one valid output.

Sample Input 2

3 6
1 2 1
1 3 0
2 1 1
2 3 0
3 1 1
3 2 0

Sample Output 2

-1

Suppose villagers 2 and 3 are confused.

In this case, there are 2^3=8 possible combinations for whether each villager is honest or a liar. Among them, for example, if villager 1 is an honest villager who is not confused, villager 2 is a confused liar, and villager 3 is a confused honest villager, then according to the rules, villager 2 should tell the truth, but they falsely testify that villager 1 is a liar.

You can confirm that also in other combinations, there will be some testimonies that violate the rules.

Therefore, if villagers 2 and 3 are confused, the given set of testimonies contradicts.

In fact, in this test case, no matter which villagers are confused, the given set of testimonies contradicts.

Sample Input 3

3 0

Sample Output 3

000

There may be any number of confused villagers, possibly zero or all.