3016 - 部落领导者

题目描述

部落准备迁移到新的牧场,迁移到新的的牧场之前,部落迎来了新的一届领导者推举。

部落推举领导者的方式非常简单,部落中每个人说出自己信任哪些人。如果某人被除了自己以外的其他所有人直接或简间接的信任了,这个人就可以成为部落领导者。

例如,如果族人 X 信任 YY 信任 Z,那么 X 直接的信任了 Y,间接的信任了 ZY 直接或间接信任的人将被 X 间接信任。当然,每个人都是信任自己的。这种推举方式会使得部落可能会产生多个领导人,这也是能被部落中的族人接受的。

给定部落中族人之间的信任关系,请编程计算出,本次推举,会产生多少个部落领导者。

输入

第一行:两个用空格分开的整数:NM,表示部落有 N 个人(编号为 1 \sim N),有 M 个信任关系。

接下来 M 行,每行读入 2 个整数 X_iY_i,表示 X_i 直接信任 Y_i

输出

输出推举出的部落领导者的人数。

样例

输入

3 3
1 2
2 3
1 3

输出

1

输入

3 2
1 2
2 1

输出

0

输入

6 9
1 2
2 3
3 1
4 5
3 5
5 6
2 4
6 4
5 6

输出

3
说明

【数据范围】

对于 100\% 的数据,1\le N \le 10^41 \le M \le 5 \times 10^41 \le X_i,Y_i \le N

请注意:测试数据中存在重复的关系。

来源

东方博宜OJ

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 69
通过人数 52
金币数量 3 枚
难度 提高


上一题 下一题