问题描述

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$ 条信息相符，则可以输出其中任意一个答案。

约束条件

• $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$ 分) 没有额外的约束。

输入

输入以以下格式从标准输入读取：

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$) 输出议员 $i$ 是否为间谍，如果是则输出 1，否则输出 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 是唯一正确的答案。注意，非间谍的议员的证言可能是真实的，也可能是虚假的。