Page not loading? Try clicking here.
Placeholder

#5886
Subtask
Grading on hold

마피아 게임 2s 1024MB

Problems

마피아 게임은 서로의 정체를 알 수 없는 시민이 심문을 통해 서로의 정체를 알고 있는 마피아를 찾아내는 게임이다.

1에서 N까지 번호가 매겨진 N 명의 플레이어가 마피아 게임을 시작한다.

각 플레이어 i (1 ≤ i ≤ N)에 대해 다음과 같은 정보가 있다.

  • T_i = 1 일 때, 플레이어 i는 마피아다.

  • T_i = 2 일 때, 플레이어 i는 마피아가 아닌 시민이다.

  • T_i = 3 일 때, 플레이어 i가 마피아인지 여부가 불분명하다.

마피아 게임이 시작되고 대화를 통해 M 개의 정보가 추가되었다.

j (1 ≤ j ≤ M) 번째 정보는 플레이어 A_j (1 ≤ A_j ≤ N)가 "플레이어 B_j (1 ≤ B_j ≤ N)는 마피아이며 플레이어 C_j (1 ≤ C_j ≤ N)는 마피아가 아니다”라고 말했다는 것이다.

만약 A_j가 마피아라면 j 번째 정보는 사실과 다르다. 즉, A_j가 마피아라면, "B_j는 마피아다", "C_j는 마피아가 아니다"중 적어도 하나는 사실이 아니다.

한편, A_j가 마피아가 아니고 시민인 경우, j 번째의 정보는 사실일 수도 있고, 그렇지 않을 수도 있다. 즉, 시민의 말의 진위 여부는 중요하지 않다.

주어진 총 N + M 개의 정보가 모순되는지 여부를 판정하고, 모순되지 않는 경우, 각각의 플레이어가 마피아인지를 출력하는 프로그램을 작성하시오.

N + M 개의 정보와 일치하는 여러 대답이 있으면 그 중 하나를 출력 할 수 있다.


Input

입력은 다음 형식으로 표준 입력에서 제공됩니다.

N M

T_1 T_2 … T_N

A_1 B_1 C_1

A_2 B_2 C_2

:

A_M B_M C_M

[제한]

1 ≤ N ≤ 300\,000

1 ≤ M ≤ 300\,000

1 ≤ T_i ≤ 3 (1 ≤ i ≤ N)

1 ≤ A_j ≤ N (1 ≤ j ≤ M)

1 ≤ B_j ≤ N (1 ≤ j ≤ M)

1 ≤ C_j ≤ N (1 ≤ j ≤ M)

A_j ≠ B_j (1 ≤ j ≤ M)

A_j ≠ C_j (1 ≤ j ≤ M)

B_j ≠ C_j (1 ≤ j ≤ M)


Output

주어진 정보가 모순되면 -1을 한 줄로 출력한다.

그렇지 않으면 출력은 N 행으로 구성된다.

i (1 ≤ i ≤ N) 번째 줄은 플레이어 i가 마피아 인 경우 1을 출력하고 플레이어 i가 마피아가 아닌 경우 2를 출력한다. N + M 정보와 일치하는 여러 대답이 있으면 그 중 하나를 출력 할 수 있다.


Subtask

# Score Condition
#17

N \le 16, M \le 100

#238

N \le 3\,000, M \le 3\,000

#355

추가 제한 없음


Example #1

4 1
1 3 2 3
1 2 3
1
2
2
1

플레이어 1은 마피아이기에 "1 2 3"이라는 정보에 대해 플레이어 2가 마피아가 아니거나 플레이어 3이 마피아여야 한다.

플레이어 3이 마피아가 아니기에 플레이어 2가 마피아가 아니어야 한다.

이에 답은 "1 2 2 1" 혹은 "1 2 2 2"가 된다.


Example #2

4 2
2 1 3 1
4 3 1
2 4 3
-1

플레이어 4는 마피아이기에 "4 3 1"이라는 정보에 대해 플레이어 3이 마피아가 아니거나 플레이어 1이 마피아여야 한다.

그러나, 플레이어 1은 마피아가 아니기에 플레이어 3이 반드시 마피아가 아니여야 한다.

두 번째 정보인 "2 4 3"의 경우 플레이어 4가 마피아가 아니거나 플레이어 3이 마피아여야한다.

그러나, 플레이어 4는 마피아이기에 플레이어 3이 반드시 마피아여야 한다.

두 정보가 모순되기에 -1을 출력한다.


Example #3

3 2
1 2 2
2 1 3
2 3 1
1
2
2

시민의 증언은 진위 여부가 중요하지 않다.


Source

JOI 2021 예선2

You must sign in to write code.