该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$TooY0ung$ 给出一幅无向图，图中有 $n$ 个顶点，$m$ 条边。点的编号为 $1-n$ ，边的编号为 $1-m$。

给出每条边连通的情况，第 $i$ 条边连接着点 $xi$ 和点 $yi$。

现在，给你三种颜色，黑色，蓝色，绿色，希望你对点进行染色，要求相邻（被一条边相连）的点颜色不能相同。

颜色不必全部使用，求一共有多少种染色方案。

输入格式

输入文件名为color.in。

输入文件包含多行，第一行输入两个非负整数，$n$ 和 $m$，含义见题目描述。

接下来输入 $m$ 行，每行两个数字 $xi$ 和 $yi$，表示每条边链接点的编号。数据随机生成，且数据保证输入的图中没有重边和自环。

输出格式

输出文件名为color.out。

输出包含一行，一个数字，表示答案。

3 3
1 2
2 3
3 1

6

4 0

81

5 5
3 2
5 1
4 3
4 1
2 1

36

样例1解释

有3个点，3条边，染色方案如下：

黑绿蓝，黑蓝绿，绿黑蓝，绿蓝黑，蓝黑绿，蓝绿黑。

共6种。

样例2解释

图中没有边，可以随意染色，答案为$3*3*3*3 = 81$。

数据规模与约定

对于30%的测试数据，$1\le n\le10，1 \le xi,yi \le n，0 \le m \le n*(n-1)/2$。

对于100%的测试数据，$1 \le n \le 20，1 \le xi,yi \le n，0 \le m \le n*(n-1)/2$。