Bessie's Morning Run

Bessie the cow has realized that in order to maintain her figure she needs more exercise. She now wants to pick a running route on her farm. The farm consists of \(n\) fields (numbered from 1 to \(n\)) connected by \(m\) bidirectional roads. Conveniently, among these roads exactly \(n-1\) of them are designated as regular roads, and they form a spanning tree (i.e. from any field one can reach every other field using only regular roads). The remaining roads are non-regular.

Bessie thinks her morning run will be more entertaining if she includes some non‐regular roads. However, because she feels comfortable on regular roads, she doesn’t want to use too many non‐regular ones. After some thought, she decides that a good route is one which forms a simple cycle (a cycle that does not visit any field more than once, except for the starting/ending field) and contains exactly two non-regular roads (all other roads on the cycle are regular). Two cycles are considered the same if they consist of the same set of roads.

Given the description of the farm and its roads, count the number of good routes available to Bessie.

Note: All formulas are in \(\LaTeX\) format. For example, the spanning tree condition is written as: the first \(n-1\) roads form a spanning tree of the \(n\) fields, and a route is good if it is a simple cycle that contains exactly two non-regular roads.

inputFormat

The first line contains two integers \(n\) and \(m\) \((3 \le n \le 1000,\; n-1 \le m \le \min\{1000, \frac{n(n-1)}{2}\})\), representing the number of fields and roads respectively. The next \(m\) lines each contain two integers \(u\) and \(v\) \((1 \le u, v \le n,\; u \ne v)\), indicating a bidirectional road between fields \(u\) and \(v\). It is guaranteed that the first \(n-1\) roads are the regular roads and form a spanning tree of the \(n\) fields, while the remaining \(m - (n-1)\) roads are non-regular.

outputFormat

Output a single integer representing the number of good routes available to Bessie.

sample

4 4
1 2
2 3
3 4
1 3

0