Migrated from Lutece 2442 给小马染色

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

小兔子是坏小兔子，因为他总会在上课的时候选择摸鱼。

今天上课，小兔子又发现了一款神奇的游戏。

游戏是创造类型的，每一关卡都会给你 $n$ 只马，小兔子会给每一只马涂上颜色，黑色或者白色，其中会有 $m$ 对马会生出小马，会有以下三种情况：

1. 黑马与黑马会生出小黑马；

2. 白马与白马会生成小白马；

3. 黑马与白马会生成小斑马。

不要问我为什么能生出小斑马，也不要问我怎么生出小马的，我不知道我不知道......

小兔子不想看到在小马中看到小黑马，那么小兔子一共有多少种涂色方式呢？

Input

第一行两个数 $n,m$，表示 $n$ 只马、$m$ 对关系。 接下俩 $m$ 行，每一行两个数 $a, b$，表示第 $a$ 只马和第 $b$ 只马会生出一个小马。

Output

输出一个整数，代表答案。

Samples

3 3
1 2
1 3
2 3

4

Constraints

$1\leq n\leq 40, 0\leq m \leq \frac{n(n-1)}{2}$ $1\leq a, b\leq n\ (a \neq b)$

Resources

2020 UESTC ICPC Training for String and Search Algorithm