Geppetto's Pizza

Interview

Time limit1sMemory limit64 MB

Summary

Count the subsets of up to 20 ingredients that contain none of the given incompatible pairs, including the empty pizza.

Level: Medium4 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

Geppetto has opened the best pizza place in town. The ingredients he can put on a pizza are numbered $1$ through $N$ , and he builds each pizza by choosing any set of them.

The trouble is that some ingredients do not mix. There are $M$ pairs of ingredients that cannot sit on the same pizza. Neither pair may appear together on one pizza.

Count how many different pizzas Geppetto can make. Two pizzas are different if some ingredient $i$ is on one of them and not on the other. A pizza with no ingredients at all counts as one pizza.

Input

The first line contains two integers $N$ and $M$ separated by a space. ( $1 \le N \le 20$ , $0 \le M \le 400$ )

Each of the next $M$ lines contains two different integers $a$ and $b$ . ( $1 \le a, b \le N$ ) Ingredient $a$ and ingredient $b$ cannot be on the same pizza. The same pair may be given more than once.

Output

Print the number of different pizzas Geppetto can make.

Examples3

Example 1
Input
```
3 2
1 2
2 3
```
Expected output
```
5
```
Example 2
Input
```
3 0 
```
Expected output
```
8
```
Example 3
Input
```
3 3
1 2
1 3
2 3
```
Expected output
```
4
```