AT_mujin_pc_2016_c オレンジグラフ

[problemUrl]: https://atcoder.jp/contests/mujin-pc-2016/tasks/mujin_pc_2016_c ### Problem You are given an undirected graph with $N$ vertices and $M$ edges. It is connected and has no self-loops nor parallel edges. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $M$. Initially, all the edges are white. You repeat the following operation: Choose a white edge and paint it in orange. However, you are not allowed to apply an operation that yields an odd-length cycle that consists only of orange edges. You repeat the procedure until there is no valid operation. Your task is, given the initial graph, to compute the number of possible outcomes (i.e., the colors of the edges).

### Input The input is given from the standard input in the following format. ``` $N$ $M$ $x_1$ $y_1$ $x_2$ $y_2$ $:$ $x_M$ $y_M$ ``` - In the first line, integers $N$ ($2≦N≦16$) and $M$ ($N-1≦M≦N(N-1)/2$) are written, separated by a space. $N$ and $M$ describe the numbers of vertices and edges, respectively. - The subsequent $M$ lines describe the edges. The $i$\-th line among them contains two integers $x_i$ and $y_i$ ($1≦x_i < y_i≦N$), separated by a space, which indicates the endpoints of edge $i$. - If $i≠j$, then $x_i≠x_j$ or $y_i≠y_j$. - The graph is connected.

### Output Output the number of possible outcomes, i.e., the number of the possible sets of orange edges. Put the newline at the end of the output.