题目描述

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$ 条信息均一致的答案，输出其中任意一个即可。

4 1
1 3 2 3
1 2 3

1
2
2
1

4 2
2 1 3 1
4 3 1
2 4 3

-1

3 2
1 2 2
2 1 3
2 3 1

1
2
2

提示

样例 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 分）无额外约束。