P7157 "dWoi R1" Physics Problem

Facing the physics problem on the whiteboard, Wang Ma fell into deep thought ....

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.**

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 one integer in one line, representing how many "升降华" relations there are.

#### 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$): ```cpp 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