← 返回题目列表

AtCoder · mujin_pc_2016_c

C. 橙色图

中文机器翻译题面 查看原题

问题

给你一个无向图 N 顶点和 M 边缘。它是连通的,没有自环,也没有平行边。顶点编号从 1 to N,边的编号从 1 to M.

最初,所有边缘都是白色的。您重复以下操作:选择一条白色边缘并将其涂成橙色。但是,您不能应用产生仅由橙色边组成的奇数长度循环的运算。

重复该过程,直到没有有效操作。您的任务是,给定初始图,计算可能结果的数量(即边的颜色)。


输入

输入由标准输入按以下格式给出。

N M
x_1 y_1
x_2 y_2
:
x_M y_M
  • 第一行,整数 N (2≦N≦16) 和 M (N-1≦M≦N(N-1)/2) 被写入,用空格分隔。 N 和 M 分别描述顶点和边的数量。
  • 后续 M 线描述边缘。 i其中第行包含两个整数 x_i 和 y_i (1≦x_i<y_i≦N),用空格分隔,表示边的端点 i.
  • If i≠j,那么 x_i≠x_j or y_i≠y_j.
  • 该图已连接。

输出

输出可能结果的数量,即可能的橙色边集合的数量。将换行符放在输出的末尾。


输入示例 1

3 3
1 2
1 3
2 3

输出示例 1

3

存在三种可能的结果,如下图所示。


输入示例 2

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

输出示例 2

5

有五种可能的结果,如下图所示。


输入示例3

5 4
1 2
2 3
3 4
4 5

输出示例 3

1

有一种可能的结果,如下图所示。