Rikka와 게임 이론

게임 이론은 컴퓨터 과학에서 흥미로운 주제이다.

SG 함수는 게임 이론의 중요한 개념이다. 정점 집합 $V_1$과 간선 집합 $E_1$을 가진 방향 비순환 그래프 $G_1$이 주어지면, 각 정점 $u \in V_1$의 SG 함수 $sg(u)$는 다음과 같이 정의된다:

$sg(u) = \text{mex}(\{sg(v) \mid (u,v) \in E_1\})$

여기서 음이 아닌 정수의 집합 $S$에 대해 $\text{mex}(S)$는 $S$에 속하지 않는 가장 작은 음이 아닌 정수이다.

Rikka는 SG 함수를 무방향 그래프로 일반화하려고 한다. 정점 집합 $V$와 간선 집합 $E$를 가진 무방향 그래프 $G$가 주어질 때, $V$ 위의 함수 $f$가 다음 조건을 모두 만족하면 $f$를 $G$의 유효한 SG 함수라고 한다:

• 각 정점 $u \in V$에 대해 $f(u)$는 음이 아닌 정수이다.
• 각 정점 $u \in V$에 대해 $f(u) = \text{mex}(\{f(v) \mid (u,v) \in E\})$이다.

그래프에는 유효한 SG 함수가 여러 개 있을 수 있다. Rikka는 이 함수들이 서로 어떤 관계가 있는지 알고 싶어 한다. 첫 단계로, 주어진 무방향 그래프 $G$의 유효한 SG 함수의 개수를 구하라.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \leq n \leq 17$, $0 \leq m \leq \frac{n(n-1)}{2}$).

이어서 $m$개의 줄에 각각 간선의 두 정점 $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$)가 주어진다. 자기 루프와 중복 간선은 없다.

유효한 SG 함수의 개수를 한 줄에 출력한다.

간단하게 나타내기 위해 함수 $f$를 리스트 $[f(1), \dots, f(n)]$으로 쓴다.

예시 입력에 대해 유효한 SG 함수는 6개이다: $[0,1,0,1,0]$, $[0,1,2,0,1]$, $[0,2,1,0,1]$, $[1,0,1,0,1]$, $[1,0,1,2,0]$, $[1,0,2,1,0]$.