哆啦A梦的道路修改灯

哆啦A梦的道路修改灯

题目描述:

在 22 世纪,人们喜欢穿越到战国时代生活。

一天,大雄想回到战国时代体验生活,他哭诉着请求哆啦A梦带他回到战国时代,在大雄的哭声“攻击”下,多啦A梦只能带着他乘坐时光机回到战国时代。

当他们到达战国时代后,他们看了一眼这个时期的地图,他们看到了 \(66\) 个国家的战略地图,现在,他们位于德川幕府,由于他们的服饰过于奇怪,他们被德川幕府扣押了。现在,他们想前往其他国家,可现在恰逢道路改革,德川幕府要对每个乡之间的道路进行整改,当前的德川幕府统治下的国家有 \(n\) 个乡,他们之间一共有 \(m\) 条道路,这些道路被视作双向道路(可以从两端互相到达彼此),本题**不保证**所有的乡都是互通的(从任意一个乡可以到达任意一个乡)。德川幕府决定将这些道路修改为单向道路(只能从一端到达另一端),这是一个巨大的工程。现在,多啦A梦与德川佳康商量,如果他们将这些道路改革完成后,德川佳康就放他们离开,德川佳康同意了。

这时,多啦A梦准备开始进行道路改革了,他拿出了自己的道路修改灯,被这个道具照射一下,当前的双向道路就会变成单向道路,现在德川佳康想知道在道路改革后,最少会有多少个乡出现 \(lonely\) 现象(如果一个乡没有道路到达这里,就称其为 \(lonely\) 的)。

输入描述

第一行输入两个数 \(n\),\(m\),分别表示乡的数量和道路的数量 \((2 \le n \le 10^5, \space 1 \le m \le 10^5)\)
接下来 \(m\) 行,每行两个数 \(u\),\(v\),分别表示与第 \(i\) 个道路相互连接的乡的编号 \((1 \le u,v \le n, \space u \not= v)\)

输出描述

输出一个整数 \(ans\),表示 \(lonely\) 的乡的数量

样例

输入

4 3
2 1
1 3
4 3

输出

1

样例解释

对于这个样例,这些道路可能的路线是 \(1 \rightarrow 2, \space 1 \rightarrow 3, \space 3 \rightarrow 4\)

信息

ID
1001
难度
9
分类
平面图 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
上传者