P14334 [JOI2021 预选赛 R2] 间谍 2 / Spy 2

JOI 国有 $ N $ 名议员，编号从 1 到 $ N $。作为 JOI 国的大臣，你试图找出议员中的间谍。你已获得关于每名议员 $ i $（$ 1 \le i \le N $）的如下信息： - 若 $ T_i = 1 $，则议员 $ i $ 是间谍。 - 若 $ T_i = 2 $，则议员 $ i $ 不是间谍。 - 若 $ T_i = 3 $，则议员 $ i $ 是否为间谍尚不明确。 此外，通过进一步调查，你获得了 $ M $ 条新信息。第 $ j $ 条调查信息（$ 1 \le j \le M $）表示：议员 $ A_j $（$ 1 \le A_j \le N $）声称“议员 $ B_j $（$ 1 \le B_j \le N $）是间谍，且议员 $ C_j $（$ 1 \le C_j \le N $）不是间谍”。 但需注意：若议员 $ A_j $ 是间谍，则第 $ j $ 条调查信息中的陈述与事实不符。换言之，若议员 $ A_j $ 是间谍，则“议员 $ B_j $ 是间谍”和“议员 $ C_j $ 不是间谍”这两项陈述中至少有一项为假。另一方面，若议员 $ A_j $ 不是间谍，则第 $ j $ 条调查信息中的陈述可能为真，也可能为假。 给定所有议员的初始信息以及调查结果，请编写程序判断这 $ 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 \le i \le N $）输出 1 表示议员 $ i $ 是间谍，输出 2 表示议员 $ i $ 不是间谍。若存在多个与 $ N + M $ 条信息均一致的答案，输出其中任意一个即可。

### 样例 1 解释 在输出样例 1 中，议员 1 是间谍，其陈述“议员 2 是间谍，且议员 3 不是间谍”因议员 2 并非间谍而与事实不符。因此，输出样例 1 与所给信息一致，为正确答案。 此外，“仅议员 1 是间谍，其余议员均不是间谍”这一答案也同样是正确的。 ### 样例 2 解释 若假设议员 3 是间谍，则与第一条调查信息矛盾；若假设议员 3 不是间谍，则与第二条调查信息矛盾。由于信息存在矛盾，应输出 $ -1 $。 ### 数据范围 - $ 1 \le N \le 300\,000 $。 - $ 1 \le M \le 300\,000 $。 - $ 1 \le T_i \le 3 $（$ 1 \le i \le N $）。 - $ 1 \le A_j \le N $（$ 1 \le j \le M $）。 - $ 1 \le B_j \le N $（$ 1 \le j \le M $）。 - $ 1 \le C_j \le N $（$ 1 \le j \le M $）。 - $ A_j \ne B_j $（$ 1 \le j \le M $）。 - $ A_j \ne C_j $（$ 1 \le j \le M $）。 - $ B_j \ne C_j $（$ 1 \le j \le M $）。 ### 子任务 1. （7 分）$ N \le 16 $，$ M \le 100 $。 2. （38 分）$ N \le 3\,000 $，$ M \le 3\,000 $。 3. （55 分）无额外约束。