Description

Geppetto opened a pizza shop, and he is trying hard to make the best pizza in the whole city.

Geppetto uses $N$ kinds of ingredients to make pizza, and there is only one of each kind. The ingredients are numbered from $1$ to $N$. Making a pizza is simple: just mix the ingredients and bake them in the oven. However, Geppetto found that there are $M$ pairs of ingredients that conflict. If a pair of conflicting ingredients is mixed in the same pizza, the pizza will become very bad. This causes him extra trouble.

Geppetto wants to know the maximum number of different pizzas he can make. If one pizza contains the ingredient numbered $i$ while another pizza does not, then these two pizzas are different.

Input Format

The first line contains two integers $N, M$, representing the total number of ingredients and the number of conflicts.

The next $M$ lines each contain two integers $x_i, y_i$, representing the numbers of the two ingredients in a conflicting pair.

Output Format

Print one integer: the maximum number of different pizzas Geppetto can make.

3 2
1 2
2 3

5

3 0

8

3 3
1 2
1 3
2 3

4

Hint

[Sample 1 Explanation]

Geppetto can make the following 4 kinds of pizzas:

1

2

3

1 3

However, since Geppetto can also choose to use no ingredients, he can make at most 5 kinds of pizzas.

[Sample 2 Explanation]

There are no ingredient conflicts, so in total he can make $2^3=8$ kinds of pizzas.

[Sample 3 Explanation]

Since all ingredients conflict with each other, Geppetto can only use one ingredient or no ingredients, so in total he can make $1+3=4$ kinds of pizzas.

[Constraints]

For $100\%$ of the testdata, $1\le N\le 20，0\le M\le 400，1\le x_i,y_i\le N$, and it is guaranteed that $x_i\ne y_i$.

[Notes]

The scoring of testdata follows the original problem, with a full score of 80.

Translated from COCI 2015-2016 CONTEST #2 T2 GEPPETTO.

Translated by ChatGPT 5