题目描述

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

数据范围

• $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$ 分) 无额外限制。

输入格式

输入由标准输入按以下格式给出：

$N$ $M$
$T_{1}$ $T_{2}$ $\dots$ $T_{N}$
$A_{1}$ $B_{1}$ $C_{1}$
$A_{2}$ $B_{2}$ $C_{2}$
$:$
$A_{M}$ $B_{M}$ $C_{M}$

输出格式

输出到标准输出。

如果给定的信息存在矛盾，以 $1$ 行输出 -1。

否则，输出由 $N$ 行组成。在第 $i$ 行 ($1 \le i \le 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$ 不是间谍，“议员 $2$ 是间谍，且议员 $3$ 不是间谍”这一证词与事实不符。因此，样例输出 $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$ 是唯一的正确答案。请注意，不是间谍的议员的证词可能是事实，也可能不是事实。