Edge Move in Cactus Graph

This is the \(20\text{-th}\) Northeastern European Regional Contest (NEERC). Cactus problems have become a NEERC tradition. The first Cactus problem was given in \(2005\), so there is a jubilee – 10 years of Cactus.

A cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively, a cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed in a cactus.

You are given a cactus. An edge move is defined as follows: remove one edge from the graph and then add a new edge connecting a different pair of vertices (an edge that did not originally exist) such that the resulting graph is still a cactus. Count the number of ways to perform such a move.

For example, in one cactus (the first sample), there are \(42\) ways to perform an edge move. In the classical NEERC cactus (the second sample), there are \(216\) ways to perform a move.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq 50)\) — the number of vertices and edges of the cactus.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1 \le u, v \le n,\; u \neq v)\) representing an edge connecting vertices \(u\) and \(v\). It is guaranteed that the given graph is a cactus.

outputFormat

Output a single integer, the number of ways to perform an edge move so that the resulting graph is still a cactus.

sample

3 3
1 2
2 3
3 1

0