P7157 「dWoi R1」Physics Problem

面对白板上的物理题，王马陷入了沉思 ……

有 $n$ 个状态，编号为 $1$ 到 $n$。这 $n$ 个状态之间有 $k$ 种转换关系，第 $i$ 个转换关系描述为：第 $u_i$ 个状态和第 $v_i$ 个状态可以进行转换。当两个状态之间没有直接的转换关系但有间接的转换关系时，那么这两个状态之间有升降华关系。 求有多少个升降华关系。 **王马不会做很难的物理题，所以保证一个状态一定可以通过直接或间接的转换为另一个任意状态。**

无

无

#### 样例 1 解释 一共有 $3$ 个状态，编号为 $1,2,3$，第 $1$ 个状态和第 $2$ 个状态之间有转换关系，第 $2$ 个状态和第 $3$ 个状态之间有转换关系，第 $1$ 个状态和第 $3$ 个状态之间没有直接的转换关系，但可以用第 $2$ 个状态做桥梁进行转换，所以第 $1$ 个状态和第 $3$ 个状态之间有升降华关系。只有这一个升降华关系，输出 $1$。 #### 数据规模与约定 **本题采用捆绑测试。** - 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）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,k \le 10^7$，$1 \le u_i,v_i \le n$。 保证 $u_i \ne v_i$ 且不存在 $i \ne j ∧(u_i =u_j∧v_i=v_j)$ 和 $i \ne j∧(u_i=v_j∧u_j=v_i)$。 这句话也可以理解为无重边无自环。 #### 提示 注意，对于下面这种情况（`a - b` 代表 $a$ 能与 $b$ 互相转换）： ```cpp 1 - 2 2 - 3 1 - 3 ``` 第 $1$ 个状态和第 $3$ 个状态算有直接转换关系，即转换关系取“最短路”。