1520：【例 1】分离的路径

题目描述

为了从 $F$ 个草场中的一个走到另一个，贝茜和她的同伴们不得不路过一些她们讨厌的可怕的树。奶牛们已经厌倦了被迫走某一条路，所以她们想建一些新路，使每一对草场之间都会至少有两条相互分离的路径，这样她们就有多一些选择。

每对草场之间已经有至少一条路径，给出所有 $R$ 条双向路的描述，每条路连接了两个不同的草场，请计算最少的新建道路的数量。

路径由若干道路首尾相连而成，两条路径相互分离，是指两条路径没有一条重合的道路，但是两条分离的路径上可以有一些相同的草场。

对于同一对草场之间，可能已经有两条不同的道路，你也可以在它们之间再建一条道路，作为另一条不同的道路。

输入格式

第一行输入两个整数 $F$ 和 $R$；

接下来 $R$ 行，每行输入两个整数，表示两个草场，它们之间有一条双向道路。

输出格式

输出最少需要新建的道路数目。

样例

样例输入 #1

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

样例输出 #1

2

样例解释 #1

• 草场数 $F=7$，现有道路数 $R=7$。
• 现有道路：
  1. $1-2$
  2. $2-3$
  3. $3-4$
  4. $2-5$
  5. $4-5$
  6. $5-6$
  7. $5-7$
• 原图如下（实线为已有道路）：

  1 — 2 — 3
      |   |
  6 — 5 — 4
      |
      7
  

• 需要添加最少的道路，使得任意两个草场之间都存在两条边不相交的路径（即图是边双连通的）。
• 添加两条新道路（图中虚线）：
  1. $1-6$
  2. $3-7$ 或 $4-7$ 等
• 添加后，任意两个草场之间都有两条边不相交的路径。例如：
  • 草场 $1$ 和 $2$：$1-2$ 和 $1-6-5-2$
  • 草场 $1$ 和 $4$：$1-2-3-4$ 和 $1-6-5-4$
  • 草场 $3$ 和 $7$：$3-4-7$ 和 $3-2-5-7$
• 添加 $2$ 条道路是最少的。

数据范围

• $1 \le F \le 5000$
• $F-1 \le R \le 10000$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是边双连通分量缩点（桥缩点）的经典问题。首先求出原图的所有桥（割边），然后进行边双连通分量缩点，得到一棵树（因为原图连通）。在树中，需要添加最少的边使树变为边双连通图（即没有桥）。结论：最少需要添加的边数为 $\lceil \frac{\text{叶子节点数}}{2} \rceil$（叶子节点指缩点后树中度数为 $1$ 的节点）。证明：每次选择两个叶子节点连接一条边，可以减少两个叶子节点，直到叶子数 $\le 2$。注意如果叶子数为 $1$，则需添加一条边连接该叶子到任意点（但此时原图可能已经边双连通？实际上叶子数不会为 $1$，因为树至少有两个叶子）。