← 返回题目列表

AtCoder · arc188_c

C. 诚实或撒谎或困惑

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有一个村庄 N 村民编号为 1 to N。 每个村民要么是诚实的,要么是骗子。此外,一些村民也感到困惑。

您已获得 M 村民的证词。每个证词均由 A_i, B_i, C_i 为 i=1,2,\ldots,M,代表:

  • If C_i=0,村民 A_i 作证,村民 B_i 很诚实。
  • If C_i=1,村民 A_i 作证,村民 B_i 是个骗子。

所有村民都知道其他村民是诚实的还是骗子,并且您知道他们按照以下规则向您作证:

  • 一个不迷茫的诚实村民总是说实话。
  • 不糊涂的骗子总是说谎。
  • 一个困惑的诚实村民总是说谎。
  • 糊涂的骗子总是说实话。

也就是说,如果不糊涂,诚实的村民总是说真话,骗子总是说谎,但如果糊涂了,那就反过来了。

你决定猜测困惑的村民的集合。 给困惑的村民一个选择,这组证词是否“矛盾”就被确定了。 在这里,如果无论你如何分配村民的诚实或撒谎状态,至少有一个证词违反了村民的证词规则,则称一组证词是矛盾的。

找到一组困惑的村民,使得给定的一组证词不矛盾。 如果不存在这样一组困惑的村民,请指出这一事实。

约束

  • 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 为 i \neq j.
  • C_i = 0 or 1.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

输出

如果存在一组困惑的村民,使得给定的一组证词不矛盾,则打印一个长度的字符串 N 代表一群困惑的村民。在这个字符串中, 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 很诚实。

因此,所有给出的证言均符合村民的证言规则,因此 010,表示只有村民 2 很混乱,是一个有效的输出。


示例输入 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

可能有任意数量的困惑村民,可能是零个或全部。