스파이 2

문제

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} \neq B_{j}$ ($1 \le j \le M$).
• $A_{j} \neq C_{j}$ ($1 \le j \le M$).
• $B_{j} \neq 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$ 이 유일한 정답이 된다. 스파이가 아닌 의원의 증언은 사실일 수도 있고 그렇지 않을 수도 있음에 주의하시오.