题目描述

有一个n个点m条边的无向图。节点的编号为1到n，现在要给每个点染色，颜色从红、绿、蓝三种中选择一种。 需要满足任意有边相连的两个点染的颜色不同。求方案数。

输入数据

第一行为两个整数n,m。
接下来 m 行，每一行包括两个整数 a,b 表示有一条边连接 a和 b。
输入保证没有重边和自环。

输出数据

输出一个整数表示方案数。

样例

输入1

3 3
1 2
2 3
3 1

输出1

6

输入2

3 0

输出2

27

输入3

4 6
1 2
2 3
3 4 
2 4
1 3
1 4

输出3

0

输入4

20 0

输出4

3486784401

提示

[样例1解释]

三个点的颜色可以为:RGB ,RBG,BGR,BRG,GBR,GRB

[样例2解释]

三个点的染色可以任意染

[样例3解释]

没办法满足相连的点颜色不同

[数据范围]

$11≤n≤20$