配点: 100 点
問題文
在JOI国家 有 N 成员, 它们的编号最大为1 假设一直下雨,直到 N 。 JOI 你是国家部长,你正试图在议会成员中寻找间谍。你们都是议会议员 我获得了有关 i (1 \leqq i \leqq N的以下信息)。 当
- T_i = 1 时,该成员 i 是一名间谍。
- T_i = 2 时,该成员 i 不是间谍。 目前尚不清楚
- T_i = 3 时,该成员 i 是否是间谍。
通过进一步采访,我们发现 我们能够获得 M 条信息。j 第采访信息(1 \leqq j \leqq M) 是国会议员。 A_j (1 \leqq A_j \leqq N) 是``代表。 B_j (1 \leqq B_j \leqq N) 是一名间谍和国会议员。 C_j (1 \leqq C_j \leqq N) 不是间谍。''
然而,国会议员 如果 A_j 是间谍,那么j 采访信息中的证词与事实不符。换句话说,如果国会议员 如果 A_j 是间谍,那么 B_j 是一名间谍,”“众议员。 “ C_j 不是间谍”这一说法至少有一个是不正确的。另一方面,国会议员 当 A_j 不是间谍时, 第j 次采访信息中的证词可能真实,也可能不真实。
将提供每位议员的信息以及访谈调查的结果。 N + M 判断这些信息是否不一致,如果不一致,则编写一个程序来判断每位国会议员是否是间谍。 如果有多个答案与N + M 信息相匹配,则可以输出其中任何一个。
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq M \leqq 300\,000.
- 1 \leqq T_i \leqq 3 (1 \leqq i \leqq N).
- 1 \leqq A_j \leqq N (1 \leqq j \leqq M).
- 1 \leqq B_j \leqq N (1 \leqq j \leqq M).
- 1 \leqq C_j \leqq N (1 \leqq j \leqq M).
- A_j \neq B_j (1 \leqq j \leqq M).
- A_j \neq C_j (1 \leqq j \leqq M).
- B_j \neq C_j (1 \leqq j \leqq M).
小課題
- (7 点) N \leqq 16,M \leqq 100.
- (38 点) N \leqq 3\,000,M \leqq 3\,000.
- (55 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
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 在 1 行。
否则,输出为 N 行组成。 在i 行目 (1 \leqq i \leqq N) 是议会议员。 如果 i 是间谍 1 ,国会议员 如果 i 不是间谍 输出 2 。 如果有多个答案与N + M 信息相匹配,则可以输出其中任何一个。 国会议员
入力例 1
4 1 1 3 2 3 1 2 3
出力例 1
1 2 2 1
出力例 1 国会议员 1 是一名间谍并且 2 是一名间谍和国会议员。 3 不是间谍。” 这不是真的,因为 2 不是间谍。因此,示例输出 1 与给定信息匹配,是正确答案。
此外,国会议员 只有 1 是间谍而其他成员都不是间谍的答案也是正确的。 如果
入力例 2
4 2 2 1 3 1 4 3 1 2 4 3
出力例 2
-1
議員 3 是间谍,那么
它与第1 次采访中的信息不符。国会议员
假设 3 不是间谍,那么
它与第2 次采访中的信息不符。由于信息相互矛盾,
输出-1 。
在
入力例 3
3 2 1 2 2 2 1 3 2 3 1
出力例 3
1 2 2
入力例 3 中,所有成员都会获得无论他们是否是间谍的信息。这些与访谈调查的信息一致,因此这是输出的示例。 3 是唯一正确的答案。请注意,非间谍的证词可能是真的,也可能不是。