分数: 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
可能有任意数量的困惑村民,可能是零个或全部。