Hide

Problem G
Geppetto

Everyone’s favorite character and puppet-maker Geppetto has opened a new pizza place, the best in town. Geppetto is trying to make the best pizza possible, but at the same time he doesn’t want to have a small selection of pizzas.

He makes his pizzas out of $N$ ingredients marked with numbers from $1$ to $N$. All that would be simple if he could mix any ingredient with every ingredient on the pizza, but unfortunately, that is not the case. Sometimes some ingredients cannot mix and that creates additional complications for our pizza master.

There are $M$ pairs of ingredients that cannot be on the same pizza at the same time. Given these restrictions, Geppetto wants to know how many different pizzas he can make. Help him answer this question. Two pizzas are considered different if there is an ingredient of index $i$ that is on one pizza, but not on the other.

Input

The first line of input contains two integers $N$ and $M$ ($1 \leq N \leq 20$, $0 \leq M \leq 400$). Each of the following $M$ lines contains two different numbers $a$ and $b$, they represent the prohibition of mixing ingredients marked with $a$ and $b$ on the pizza. ($1 \leq a, b\leq N$). All pairs of ingredients are not necessarily distinct, some pair could occur multiple times.

Output

The first and only line of output must contain the number of different pizzas given the restrictions in the task.

Sample Input 1 Sample Output 1
3 2
1 2
2 3
5
Sample Input 2 Sample Output 2
3 0
8
Sample Input 3 Sample Output 3
3 3
1 2
1 3
2 3
4

Please log in to submit a solution to this problem

Log in