진실을 말하는 사람과 거짓을 말하는 사람

N명의 사람으로 이루어진 모임이 있다. 각 사람은 항상 진실만 말하는 사람 또는 항상 거짓만 말하는 사람 중 하나에 속한다.

모든 사람을 면담하여 진술을 받았다. 각 사람은 모임의 다른 구성원 몇 명을 지목하여, 그 사람이 진실을 말하는 부류에 속하는지 아니면 거짓을 말하는 부류에 속하는지를 말했다.

규칙은 다음과 같다. 진실을 말하는 사람의 모든 진술은 참이어야 하고, 거짓을 말하는 사람은 적어도 하나의 진술이 거짓이어야 한다.

각 사람에게 진실 부류 또는 거짓 부류를 배정하는 방법 중, 위 규칙을 모두 만족하는 서로 다른 배정의 개수를 구하여라.

첫째 줄에 모임에 속한 사람 수 N이 주어진다. (2 ≤ N ≤ 20)

다음 2N개의 줄에는 각 사람의 진술이 주어진다. j번째 사람의 진술은 두 줄로 이루어지며, 다음과 같은 형식이다.

K A1 A2 ... AKL B1 B2 ... BL

첫째 줄은 j번째 사람이 "진실을 말한다"고 지목한 사람들이다. K는 지목한 사람 수이고, A1, A2, …, AK는 그 사람들의 번호이다. 둘째 줄은 j번째 사람이 "거짓을 말한다"고 지목한 사람들로, L은 그 수, B1, B2, …, BL은 번호이다. 지목한 사람이 없으면 그 줄은 0만 주어진다.

사람은 1번부터 N번까지 번호가 매겨져 있다. 각 사람은 자기 자신에 대해서는 진술하지 않으며, 같은 사람을 진실과 거짓으로 동시에 지목하지 않는다.

적어도 하나의 유효한 배정이 존재함이 보장된다.

위 규칙을 모두 만족하는, 각 사람에 대한 진실/거짓 배정의 개수를 정수 하나로 출력한다.

원문은 유효한 배정 하나를 각 사람마다 true/false로 출력하도록 요구했으나, 그러한 배정은 유일하지 않을 수 있어 정확 일치 채점이 불가능하다. 그래서 답이 유일하게 정해지는 유효한 배정의 총 개수를 출력하도록 문제를 다듬었다.