題目描述

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$ 是唯一的正確答案。請注意，不是間諜的議員的證詞可能是事實，也可能不是事實。