Description

The leader of SHOI, in order to make it easier for everyone to communicate, decided to build a local area network (LAN) in the computer room where they are training. There are $n$ computer terminals in the room. The leader used $m$ network cables to build this LAN. Each cable connects two computers so that they can communicate in both directions. The network is now connected, meaning that any two computers can communicate directly or indirectly.

To ensure that all students can keep communicating through this computer network during the whole preparation period, the leader wants to know: “If some computer $\texttt{A}$ shuts down due to a failure, and at the same time some cable $\texttt{L}$ (which is not connected to $\texttt{A}$) is cut, can the other computers (except $\texttt{A}$) still remain mutually connected?”

Therefore, the leader needs you to compute the “instability” of this LAN. The instability is defined as: the total number of different ways to remove one computer from the network and cut one cable (and this cable is not incident to that computer), such that the remaining computers in the network are not fully connected (i.e., communication among them is not completely connected).

Input Format

The first line of the input contains two positive integers $n$ and $m$, representing the number of computer terminals in the network and the number of cables used to connect them.

In the next $m$ lines, each line contains two integers $x$ and $y$ describing a cable, meaning that this cable connects computers numbered $x$ and $y$, and $x \neq y$.

The input guarantees that the network is connected initially.

Output Format

Output one line containing one integer: the total number of different ways to remove one computer and cut one cable that make the network disconnected.

5 4
1 2
1 3
1 4
1 5

12

5 7
1 2
1 3
1 4
2 3
2 4
5 3
5 4

2

4 6
1 2
2 3
2 3
3 4
4 1
4 1

4

Hint

• $1 \leq n \leq 2 \times 10^3$;
• $1 \leq m \leq 2 \times 10^5$.

Translated by ChatGPT 5