Cactus Spanning Subgraph Count

A cactus graph is an undirected connected graph in which each edge belongs to at most one simple cycle. In other words, a cactus graph can be thought of as a tree that is allowed to have cycles; however, unlike a tree, a cactus graph may have more than one spanning subgraph (a spanning subgraph is a subgraph that contains all vertices and is connected).

For each simple cycle in a cactus graph with L edges, one may either keep all the edges of the cycle or remove exactly one of the edges (thus breaking the cycle but still retaining connectivity on that part). Hence, the number of ways to choose edges from that cycle is

\(L + 1\)

Since cycles in a cactus graph are edge-disjoint and the rest of the edges (the tree edges) must be kept, the total number of spanning subgraphs (also known as "cactus number") is:

\(\prod_{\text{each cycle}} (L+1)\)

If the given graph is not a cactus graph (i.e. it is either disconnected or some edge participates in more than one simple cycle), the answer is 0.

Input/Output: You are given an undirected graph. The first line contains two integers n and m which denote the number of vertices and edges, respectively. The following m lines each contain two integers u and v representing an edge between vertices u and v (vertices are 1-indexed). Output a single integer (which can be large) representing the cactus number.

inputFormat

The first line of input contains two integers n and m (1 ≤ n, m ≤ some reasonable limits) representing the number of vertices and edges in the graph. The next m lines each contain two integers u v representing an undirected edge between vertices u and v.

outputFormat

Output a single integer which is the number of spanning subgraphs of the given graph, computed as the product over every simple cycle (of L edges) of (L+1). If the graph is not a cactus graph, output 0.

sample

3 2
1 2
2 3

1