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

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

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

마피아 게임이 시작되고 대화를 통해 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 개의 정보와 일치하는 여러 대답이 있으면 그 중 하나를 출력 할 수 있다.

마피아 게임 timer 2s memory 1024MB

마피아 게임 2s 1024MB