题目描述

小明开了一家奶茶店，他正在研究新品配方。

小明有 $N$ 种原材料，每种原材料至多使用一份，编号为 $1$ 到 $N$。制作一杯奶茶很简单，只要把选中的原材料混合在一起就行了。但小明发现有 $M$ 对原材料不能同时使用，如果一对冲突的原材料混合在同一杯奶茶里，这杯奶茶就会变得十分难喝。

小明想知道他最多能做出多少种不同的奶茶。如果一杯奶茶包含编号为 $i$ 的原材料，而另一杯不包含，那么这两杯奶茶就是不同的（即使其他原材料相同）。

输入格式

第一行两个整数 $N, M$，分别表示原材料总数和冲突对数。

接下来 $M$ 行，每行两个整数 $x_i, y_i$，表示第 $x_i$ 种和第 $y_i$ 种原材料冲突。

输出格式

一行一个整数，表示小明最多能做出多少种不同的奶茶。

样例

3 2
1 2
2 3

5

3 0

8

3 3
1 2
1 3
2 3

4

提示

样例 1 解释

小明可以做出以下 $4$ 种奶茶：

1

2

3

1 3

不过因为小明可以不做奶茶（空集），所以最多可以做出 $5$ 种。

样例 2 解释

没有原材料冲突，所以一共可以做出 $2^3=8$ 种奶茶。

样例 3 解释

由于所有原材料都互相冲突，所以小明只能选一种原材料或者不选，一共可以做出 $1+3=4$ 种奶茶。

数据范围

对于 $100\%$ 的数据，$1 \le N \le 20$，$0 \le M \le 400$，$1 \le x_i, y_i \le N$，保证 $x_i \ne y_i$。