Cactus Graph Extension Problem

A cactus graph is an undirected, simple, connected graph in which every edge belongs to at most one simple cycle. In other words, for a graph \(G\), if each edge of \(G\) is contained in at most one simple cycle (a cycle that does not repeat any vertex except for the starting and ending vertex), then \(G\) is called a cactus.

JiuTiao has a simple, connected, undirected graph \(G\) with no self-loops or multiple edges. However, she feels that the graph does not have enough edges, so she wants to add some new edges. At the same time, for ease of storage, the total number of edges in the resulting graph cannot be too many. After careful consideration, she has decided that after adding some new edges, the resulting graph must be a cactus.

Two schemes of adding edges are considered different if there is at least one edge that is present in one scheme and not in the other. Your task is to count how many different valid schemes exist.

Note: The original graph is given as an undirected, simple, connected graph. You are allowed to add only those edges that are not initially present. When an edge is added to a tree (or a sparse graph), it creates a unique simple cycle (which is the union of the added edge and the unique path in the original graph between its endpoints). A set of added edges is valid if no tree edge (i.e. an edge from the original graph) is contained in more than one of these simple cycles.

Input/Output Format: See below.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq \text{small},\ m \geq n-1)\), representing the number of vertices and the number of edges in the original graph respectively. It is guaranteed that the graph is undirected, connected, without self-loops and without multiple edges.

The following \(m\) lines each contain two integers \(u\) and \(v\) \((1 \le u,v \le n)\) describing an edge between vertices \(u\) and \(v\).

You may assume that for the test cases used this problem, \(n\) is small enough to allow an exponential solution.

outputFormat

Output a single integer: the number of different valid schemes to add extra edges such that the resulting graph is a cactus.

sample

3 2
1 2
2 3

2