#T2313. 航线请求(Flight Route Requests)

航线请求(Flight Route Requests)

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

板块: Advanced Graph Problems

时限: 1.00 s | 内存: 512 MB

题目描述

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

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

输入

第一行包含两个整数 nn 和 mm:城市数量和请求数量。城市编号为 1,2,…,n1,2,\dots,n。

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

输出

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

数据范围

1≤n≤1051 \le n \le 10^5 1≤m≤2⋅1051 \le m \le 2 \cdot 10^5 1≤a,b≤n1 \le a,b \le n

样例输入

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

样例输出

4