Description

There are $n$ states, numbered from $1$ to $n$. Among these $n$ states, there are $k$ kinds of transition relations. The $i$-th transition relation is described as follows: state $u_i$ and state $v_i$ can be converted into each other. When there is no direct transition relation between two states but there is an indirect transition relation, then there is a "升降华" relation between these two states.

Find how many "升降华" relations there are.

Wang Ma cannot solve very hard physics problems, so it is guaranteed that one state can be converted to any other state through direct or indirect transitions.

Input Format

The first line contains two integers $n,k$, representing the number of states and the number of transition relations.
In the next $k$ lines, each line contains two integers $u_i,v_i$, meaning there is a transition relation between these two states.

Output Format

Output one integer in one line, representing how many "升降华" relations there are.

3 2
1 2
2 3

1

Hint

Explanation for Sample 1

There are $3$ states in total, numbered $1,2,3$. There is a transition relation between state $1$ and state $2$, and between state $2$ and state $3$. There is no direct transition relation between state $1$ and state $3$, but they can be converted using state $2$ as a bridge, so there is a "升降华" relation between state $1$ and state $3$. There is only this one "升降华" relation, so output $1$.

Constraints

This problem uses bundled tests.

• Subtask 1 (5 pts): $n \le 2$.
• Subtask 2 (10 pts): $k=n-1$, $u_i+1=v_i$.
• Subtask 3 (10 pts): $k=n-1$, $u_i=1$.
• Subtask 4 (25 pts): $n,k \le 1000$.
• Subtask 5 (50 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le n,k \le 10^7$, $1 \le u_i,v_i \le n$.

It is guaranteed that $u_i \ne v_i$, and there do not exist $i \ne j ∧(u_i =u_j∧v_i=v_j)$ and $i \ne j∧(u_i=v_j∧u_j=v_i)$.

This sentence can also be understood as: no multiple edges and no self-loops.

Hint

Note that for the following case (a - b means $a$ can be converted into $b$ and $b$ can be converted into $a$):

1 - 2
2 - 3
1 - 3

State $1$ and state $3$ are considered to have a direct transition relation, i.e. the transition relation uses the "shortest path".

Translated by ChatGPT 5