AT_mujin_pc_2016_c.オレンジグラフ

给定一个无向图，包含 $N$ 个顶点和 $M$ 条边。该图是连通的，没有自环和重边。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。

初始时，所有边都是白色的。你可以重复进行如下操作：选择一条白色的边，将其涂成橙色。但是，不能进行会导致仅由橙色边组成的奇数长度环出现的操作。

你需要重复上述操作，直到无法再进行有效操作。给定初始图，计算可能的结果数（即边的颜色方案数）。

输入由标准输入给出，格式如下：

$N$ $M$
$x_1$ $y_1$
$x_2$ $y_2$
\vdots
$x_M$ $y_M$

• 第一行包含两个整数 $N$（$2 \leq N \leq 16$）和 $M$（$N-1 \leq M \leq \frac{N(N-1)}{2}$），用空格分隔。$N$ 和 $M$ 分别表示顶点数和边数。
• 接下来的 $M$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i < y_i \leq N$），表示第 $i$ 条边的两个端点。
• 对于 $i \neq j$，有 $x_i \neq x_j$ 或 $y_i \neq y_j$。
• 保证图是连通的。

输出可能的结果数，即可能的橙色边集合的数量。输出末尾需换行。

由 ChatGPT 4.1 翻译