Problem Description

Geppetto owns a pizzeria and is striving to make the best pizza in town.

Geppetto uses $N$ ingredients to make pizzas, with each ingredient available in a single unit. The ingredients are numbered from $1$ to $N$. Making a pizza is straightforward; simply mix the ingredients and bake them in the oven. However, Geppetto has discovered that there are $M$ pairs of conflicting ingredients. If a pair of conflicting ingredients is mixed in a pizza, the pizza becomes inedible. This adds an extra challenge for him.

Geppetto wants to know the maximum number of different pizzas he can make. Two pizzas are considered different if one contains an ingredient with number $i$ and the other does not.

Input Format

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

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

Output Format

A single line containing an integer, representing the maximum number of different pizzas Geppetto can make.

Sample Input and Output

Sample Input #1

3 2
1 2
2 3

Sample Output #1

5

Sample Input #2

3 0

Sample Output #2

8

Sample Input #3

3 3
1 2
1 3
2 3

Sample Output #3

4

Notes

[Sample 1 Explanation]

Geppetto can make the following 4 pizzas:

1

2

3

1 3

However, since Geppetto can also make a pizza with no ingredients, he can make a total of 5 pizzas.

[Sample 2 Explanation]

Since there are no conflicting ingredients, Geppetto can make a total of $2^3 = 8$ pizzas.

[Sample 3 Explanation]

Since all ingredients conflict with each other, Geppetto can only make pizzas with one ingredient or no ingredients, totaling 4 pizzas.

[Data Range]

For $100\%$ of the data, $1 \le N \le 20$, $0 \le M \le 400$, $1 \le x_i, y_i \le N$, and guaranteed $x_i \ne y_i$.

[Notes]

This problem's scoring is based on the original contest, with a maximum score of 80.

The problem is translated from COCI 2015-2016 CONTEST #2 T2 GEPPETTO.

见题面 Input 部分

见题面 Output 部分