페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5886
서브태스크
채점 보류

마피아 게임 2초 1024MB

문제

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

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 개의 정보와 일치하는 여러 대답이 있으면 그 중 하나를 출력 할 수 있다.


입력

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

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)


출력

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

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

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


부분문제

번호 점수 조건
#17점

N \le 16, M \le 100

#238점

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

#355점

추가 제한 없음


예제1

입력
41
1323
123
출력
1
2
2
1

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

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

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


예제2

입력
42
2131
431
243
출력
-1

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

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

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

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

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


예제3

입력
32
122
213
231
출력
1
2
2

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


출처

JOI 2021 예선2

역링크