20804번 - Rikka with Game Theory 다국어

Game theory is an interesting subject in computer science.

SG function is an important concept in game theory. Given a directed acyclic graph $G_1$ with vertex set $V_1$ and directed edge set $E_1$, for each vertex $u \in V_1$, its SG function $sg(u)$ is defined as: $$ sg(u) = \text{mex}(\{sg(v)| (u,v) \in E_1\}) $$ where given a set $S$ of non-negative integers, $\text{mex}(S)$ is defined as the smallest non-negative integer which is not in $S$.

Today, Rikka wants to generalize SG function to undirected graphs. Given an undirected graph $G$ with vertex set $V$ and undirected edge set $E$, a function $f$ over $V$ is a valid SG function on $G$ if and only if:

• For each vertex $u \in V$, $f(u)$ is a non-negative integer;
• For each vertex $u \in V$, $f(u) = \text{mex}(\{f(v) | (u,v) \in E\})$.

Under this definition, there may be many valid SG functions for a graph. Therefore, Rikka wants to further figure out whether there is a connection between these valid SG functions. As the first step, your task is to calculate the number of valid SG functions for a given undirected graph $G$.

The first line contains two integers $n,m\ (1 \leq n \leq 17, 0 \leq m \leq \frac{n(n-1)}{2})$, representing the number of vertices and edges in the graph.

Then $m$ lines follow. Each line contains two integers $u_i,v_i\ (1 \leq u_i, v_i \leq n)$, representing an edge in the graph.

The input guarantees that there are no self-loops and duplicate edges in the graph.

Output a single line with a single integer, representing the number of valid SG functions.

For simplicity, we use list $[f(1), \dots, f(n)]$ to represent a function $f$. 

For the sample input, there are $6$ valid SG functions:

• $[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]$ and $[1,0,2,1,0]$.