火烧连船

题目描述

赤壁之战，曹军有 $n$ 艘战船，$m$ 条铁索。
每条铁索 $(x, y)$ 表示：船 $x$ 被铁索连向船 $y$（有向边）。

若船 $x$ 能通过铁索到达船 $y$，则 $x$ 着火时 $y$ 也会被引燃。

定义源头船为：没有其他船能引燃它的船（即入度为 $0$）。

火攻之后，一些铁索被烧断。要求 烧断后，源头船的集合不变。

求最多能烧断多少条铁索。

---

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $x, y$，表示一条铁索 $x \rightarrow y$。

输出格式

一个整数，表示最多能烧断的铁索数。

样例输入

12 14
1 2
1 12
2 3
3 4
4 5
5 2
6 4
6 7
6 10
7 8
8 9
9 10
10 11
11 9

样例输出

4

样例解释

原始图中有两个环：

• $2 \to 3 \to 4 \to 5 \to 2$
• $9 \to 10 \to 11 \to 9$

源头船为 $1$ 和 $6$（没有船能牵引它们）。

一种删除 $4$ 条铁索的方案（保留 $10$ 条）：

保留：

1 → 2
1 → 12
2 → 3
3 → 4
4 → 5
6 → 7
7 → 8
8 → 9
9 → 10
10 → 11

删去：

5 → 2
6 → 4
6 → 10
11 → 9

此时源头船仍是 $1$ 和 $6$，且所有船仍能被源头船到达。

可以证明 $4$ 是最大值。

数据范围

• 对于 $30\%$ 的数据：$n \le 20$，$m \le 50$
• 对于 $60\%$ 的数据：$n \le 5000$，$m \le 2 \times 10^4$
• 对于 $100\%$ 的数据：$1 \le n \le 2 \times 10^5$，$1 \le m \le 2 \times 10^5$

图中可能有重边和自环。