題目描述

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$ 係唯一嘅正確答案。請注意，唔係間諜嘅議員嘅證詞可能係事實，亦可能唔係事實。