AT_joi2021_yo2_e スパイ 2 (Spy 2)

JOI 国有 $N$ 名议员，编号从 $1$ 到 $N$。你作为 JOI 国的大臣，正在试图找出议员中的间谍。对于每位议员 $i$（$1 \leq i \leq N$），你获得了如下信息： - 当 $T_i = 1$ 时，议员 $i$ 是间谍。 - 当 $T_i = 2$ 时，议员 $i$ 不是间谍。 - 当 $T_i = 3$ 时，无法确定议员 $i$ 是否为间谍。 此外，通过进一步的调查，你又获得了 $M$ 条新信息。第 $j$ 条调查信息（$1 \leq j \leq M$）为：议员 $A_j$（$1 \leq A_j \leq N$）声称“议员 $B_j$（$1 \leq B_j \leq N$）是间谍，且议员 $C_j$（$1 \leq C_j \leq N$）不是间谍”。 但是，如果议员 $A_j$ 是间谍，则第 $j$ 条调查中的证言与事实不符。也就是说，如果议员 $A_j$ 是间谍，则“议员 $B_j$ 是间谍”和“议员 $C_j$ 不是间谍”这两句话中，至少有一句与事实不符。另一方面，如果议员 $A_j$ 不是间谍，则第 $j$ 条调查中的证言可能为真，也可能为假。 请根据每位议员的信息和调查结果，判断这 $N + M$ 条信息是否存在矛盾。如果不存在矛盾，请编写程序，确定每位议员是否为间谍。如果有多个符合所有 $N + M$ 条信息的答案，输出其中任意一个即可。

输入从标准输入读入，格式如下： > $N$ $M$ $T_1$ $T_2$ $\cdots$ $T_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

请输出到标准输出。 如果存在矛盾的信息，请输出一行 `-1`。 否则，输出 $N$ 行，第 $i$ 行（$1 \leq i \leq N$）输出 $1$ 表示议员 $i$ 是间谍，输出 $2$ 表示议员 $i$ 不是间谍。如果有多个符合所有 $N + M$ 条信息的答案，输出其中任意一个即可。

## 限制条件 - $1 \leq N \leq 300\,000$。 - $1 \leq M \leq 300\,000$。 - $1 \leq T_i \leq 3$（$1 \leq i \leq N$）。 - $1 \leq A_j \leq N$（$1 \leq j \leq M$）。 - $1 \leq B_j \leq N$（$1 \leq j \leq M$）。 - $1 \leq C_j \leq N$（$1 \leq j \leq M$）。 - $A_j \neq B_j$（$1 \leq j \leq M$）。 - $A_j \neq C_j$（$1 \leq j \leq M$）。 - $B_j \neq C_j$（$1 \leq j \leq M$）。 ## 子任务 1.（7 分）$N \leq 16$，$M \leq 100$。 2.（38 分）$N \leq 3\,000$，$M \leq 3\,000$。 3.（55 分）无额外限制。 ## 样例说明 1 在输出样例 $1$ 中，议员 $1$ 是间谍，“议员 $2$ 是间谍且议员 $3$ 不是间谍”的证言由于议员 $2$ 不是间谍，因此证言与事实不符。因此，输出样例 $1$ 满足所有给定信息，是正确答案。此外，只有议员 $1$ 是间谍，其余议员不是间谍的答案也是正确的。 ## 样例说明 2 如果议员 $3$ 是间谍，则与第 $1$ 条调查信息不符。如果议员 $3$ 不是间谍，则与第 $2$ 条调查信息不符。由于信息存在矛盾，应输出 `-1`。 ## 样例说明 3 在输入样例 $3$ 中，所有议员是否为间谍的信息都已给出，并且这些信息与调查结果一致，因此输出样例 $3$ 是唯一的正确答案。注意，非间谍议员的证言可能为真，也可能为假。 由 ChatGPT 4.1 翻译