问题 C: 新的改革

内存限制:256 MB 时间限制:2 S
题面:传统 评测方式:文本比较 上传者:
提交:30 通过:9

题目描述

Berland有n个城市,由m条双向道路连接。没有道路将一个城市连接到它自己,每对城市之间的连接不超过一条道路。你不能保证只用现有的道路就能从任何一个城市到达另一个城市。
贝兰总统决定对道路系统进行改革,并指示交通部进行这一改革。现在,每条道路都应该是单向的(只从一个城市通向另一个城市)。
为了不引起居民的极大不满,改革需要进行,以便尽可能少地出现独立的城市。如果没有道路通向一个城市,那么这个城市就被认为是孤立的,不过允许有道路从这个城市通出去。
帮助交通部找到改革后尽可能少的孤立城市。


输入格式

输入的第一行包含两个正整数,n和m--城市的数量和Berland的道路数量(2≤n≤100000,1≤m≤100000)。
接下来的m行包含道路的描述:第i条道路由两个不同的整数xi,yi决定(1≤xi,yi≤n, xi≠yi),其中xi和yi是由第i条道路连接的城市的编号。
可以保证每对城市之间不超过一条道路,但不能保证从任何城市都可以通过道路到达任何其他城市。

输出格式

打印一个整数--改革后分离的城市的最小数量。
Examples
Input
4 3
2 1
1 3
4 3
Output
1
Input
5 5
2 1
1 3
2 3
2 5
4 3
Output
0
Input
6 5
1 2
2 3
4 5
4 6
5 6
Output
1

输入样例 复制

4 3
2 1
1 3
4 3

输出样例 复制

1

数据范围与提示

在第一个样本中,允许以下道路方向。, , .
第二个样本。, , , , .
第三个样本。, , , , .