스파이 2

JOI 국에는 N명의 의원이 있으며, 1부터 N까지 번호가 붙어 있다. JOI 국의 대신인 당신은 의원 중에 숨어 있는 스파이를 찾아내려 한다. 각 의원 i (1 ≦ i ≦ N)에 대해 다음 정보를 얻었다.

• Ti = 1이면 의원 i는 스파이이다.
• Ti = 2이면 의원 i는 스파이가 아니다.
• Ti = 3이면 의원 i가 스파이인지 알 수 없다.

추가로 청취 조사를 실시하여 M개의 정보를 얻었다. j번째 조사 결과 (1 ≦ j ≦ M)는 의원 Aj (1 ≦ Aj ≦ N)가 "의원 Bj (1 ≦ Bj ≦ N)는 스파이이고, 의원 Cj (1 ≦ Cj ≦ N)는 스파이가 아니다"라고 증언했다는 내용이다.

의원 Aj가 스파이라면 j번째 증언은 사실이 아니다. 즉 Aj가 스파이이면 "Bj는 스파이이다"와 "Cj는 스파이가 아니다" 중 적어도 하나는 거짓이다. 반대로 Aj가 스파이가 아니라면 j번째 증언은 참일 수도 있고 거짓일 수도 있다.

의원들의 정보와 청취 조사 결과가 주어지면, N + M개의 정보가 서로 모순되는지 판정하라. 모순이 없다면 각 의원이 스파이인지 구하라. N + M개의 정보와 맞는 답이 여러 개라면 그중 아무거나 출력해도 된다.

입력은 표준 입력으로 다음 형식으로 주어진다.

N M
T1 T2 … TN
A1 B1 C1
A2 B2 C2
:
AM BM CM

정보가 모순되면 -1을 한 줄에 출력하라.

그렇지 않으면 N줄을 출력한다. i번째 줄 (1 ≦ i ≦ N)에는 의원 i가 스파이이면 1, 스파이가 아니면 2를 출력하라. N + M개의 정보와 맞는 답이 여러 개라면 그중 아무거나 출력해도 된다.

• 1 ≦ N ≦ 300 000.
• 1 ≦ M ≦ 300 000.
• 1 ≦ Ti ≦ 3 (1 ≦ i ≦ N).
• 1 ≦ Aj ≦ N (1 ≦ j ≦ M).
• 1 ≦ Bj ≦ N (1 ≦ j ≦ M).
• 1 ≦ Cj ≦ N (1 ≦ j ≦ M).
• Aj ≠ Bj (1 ≦ j ≦ M).
• Aj ≠ Cj (1 ≦ j ≦ M).
• Bj ≠ Cj (1 ≦ j ≦ M).