Edge Assignment in Graphs

Given an undirected graph with N vertices and M edges (the graph has no self‐loops but may have multiple edges), assign each edge to exactly one of its two endpoints. However, each vertex can have at most one incident edge assigned to it. In other words, for every edge e = (u,v), choose exactly one endpoint (u or v) so that if a vertex is chosen for more than one edge, the assignment is invalid. Compute the number of valid assignments modulo \(10^9+7\).

Explanation:
Each edge must be assigned to one of its adjacent vertices. Because a vertex can be assigned at most one edge, the assignment defines an injection from the set of edges to the set of vertices such that for every edge \(e = (u,v)\) the selected vertex is either \(u\) or \(v\). Note that if M > N then no valid assignment exists. It turns out that if we decompose the graph into connected components then every connected component can only be of one of the following types:

• A tree (with \(k\) vertices and \(k-1\) edges). In such a component, the number of valid assignments is equal to \(k\) (the number of vertices in the tree).
• A unicyclic graph (with \(k\) vertices and \(k\) edges). In such a component the number of valid assignments is \(2\).

If any connected component has more than one cycle (i.e. with \(l > k\) edges), then no valid assignment exists. The overall answer is the product of the valid assignment counts from each connected component modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of vertices and edges, respectively).

Then \(M\) lines follow, each containing two integers \(u\) and \(v\) (\(1 \le u, v \le N\)) representing an undirected edge between vertices \(u\) and \(v\). It is guaranteed that \(u \neq v\), though there may be multiple edges between the same pair of vertices.

outputFormat

Output a single integer: the number of valid assignments modulo \(10^9+7\).

sample

3 3
1 2
2 3
3 1

2