문제

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$는 스파이이고, 또한 의원 $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$이 유일한 정답이 된다. 스파이가 아닌 의원의 증언은 사실일 수도 있고 그렇지 않을 수도 있음에 주의하라.