链接: https://cses.fi/problemset/task/1699

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 座城市设有机场，但没有航班连接。给定 $m$ 个请求，要求某些路线必须可以通行。

你的任务是求出最少需要多少条单向航班连接，才能满足所有请求。

输入

第一行包含两个整数 $n$ 和 $m$：城市数量和请求数量。城市编号为 $1,2,\dots,n$。

接下来有 $m$ 行描述请求。每行包含两个整数 $a$ 和 $b$：表示必须存在一条从城市 $a$ 到城市 $b$ 的路线。每个请求都是唯一的。

输出

输出一个整数：最少的航班连接数量。

数据范围

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

样例输入

4 5
1 2
2 3
2 4
3 1
3 4

样例输出

4