AT_arc188_c.[ARC188C] Honest or Liar or Confused

有一个村庄，住着 $N$ 个村民，编号从 $1$ 到 $N$。每个村民要么是正直者，要么是说谎者。此外，有些村民处于“混乱”状态。

你获得了 $M$ 条村民的证言。对于 $i=1,2,\ldots,M$，第 $i$ 条证言由 $A_i,B_i,C_i$ 给出：

• 若 $C_i=0$，表示村民 $A_i$ 证言村民 $B_i$ 是正直者。
• 若 $C_i=1$，表示村民 $A_i$ 证言村民 $B_i$ 是说谎者。

所有村民都知道其他所有村民是正直者还是说谎者，并且他们的证言遵循如下规则：

• 未混乱的正直者一定作出真实的证言。
• 未混乱的说谎者一定作出虚假的证言。
• 混乱的正直者一定作出虚假的证言。
• 混乱的说谎者一定作出真实的证言。

也就是说，未混乱时，正直者说真话，说谎者说假话；混乱时，正直者说假话，说谎者说真话。

你想要推测出一组“混乱的村民”。一旦确定了混乱的村民集合，就能判断给定的 $M$ 条证言是否“矛盾”。这里，“证言矛盾”指的是：无论如何分配每个村民是正直者还是说谎者，总会存在某条证言违反上述规则。

请你找出一组使得所有证言不矛盾的“混乱的村民”集合。如果无论怎么选择混乱的村民集合，证言都矛盾，请指出这一点。

输入按以下格式从标准输入读入。

$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，否则为 0。

如果不存在这样的集合，输出 -1。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min\{2 \times 10^5, N(N-1)\}$
• $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$
• 所有输入均为整数

样例解释 1

假设村民 $1$ 是未混乱的正直者，村民 $2$ 是混乱的说谎者，村民 $3$ 是未混乱的正直者。此时，村民 $1$ 会如实证言村民 $2$ 是说谎者、村民 $3$ 是正直者。村民 $2$ 虽然是说谎者，但因混乱而作出真实证言，称村民 $3$ 是正直者。因此，所有证言都符合规则，所以仅村民 $2$ 混乱的 010 是一种合法输出。

样例解释 2

假设村民 $2,3$ 混乱。此时，关于每个村民是正直者还是说谎者共有 $2^3=8$ 种组合。例如，“村民 $1$ 是（未混乱的）正直者，村民 $2$ 是（混乱的）说谎者，村民 $3$ 是（混乱的）正直者”，此时村民 $2$ 按规则应作出真实证言，但他却作出了虚假证言，违反规则。对其它组合也同理。因此，若村民 $2,3$ 混乱，证言必然矛盾。实际上，在本例中，无论如何选择混乱的村民集合，证言都矛盾。

样例解释 3

混乱人数可以为任意，只要满足题意条件，$0$ 人或全员混乱也可以。

由 ChatGPT 4.1 翻译