Problem Description

A network in Country $X$ uses several links to connect several nodes. Communication between nodes is bidirectional. For security reasons, an important data packet must be forwarded exactly twice to reach its destination. The packet may be generated at any node, and we need to know how many different forwarding paths there are in this network.

The source and destination can be the same, but the intermediate nodes must be different.

For the network shown in Figure $1$:

$1 \to 2 \to 3 \to 1$ is allowed.

$1 \to 2 \to 1 \to 2$ or $1 \to 2 \to 3 \to 2$ are both invalid.

Constraints

$1 \le N \le 10000$, $0 \le M \le 100000$.

Notes

Updated on 2024/1/28: added a set of hack testdata.

Input Format

The first line of the input contains two integers $N, M$, representing the number of nodes and the number of links, respectively $(1 \le N \le 10000, 0 \le M \le 100000)$.

The next $M$ lines each contain two integers $u$ and $v$, indicating that node $u$ and node $v$ are connected $(1 \le u, v \le N, u \neq v)$.

The input guarantees that there is at most one edge between any two nodes, and there are no edges from a node to itself, i.e., there are no multiple edges or self-loops.

Output Format

Output one integer, representing the number of paths that satisfy the requirements.

3 3
1 2
2 3
1 3

6

4 4
1 2
2 3
3 1
1 4

10

Hint

Time limit: 1 second. Memory limit: 64 MB. Lanqiao Cup 2013, the 4th National Final.

Translated by ChatGPT 5