P0601

[HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛

每一头牛的愿望就是变成一头最受欢迎的牛。

现在有 nn 头牛,给你 mm 对整数 (A,B)(A, B),表示牛 AA 认为牛 BB 受欢迎。这种关系是具有传递性的:如果 AA 认为 BB 受欢迎,BB 认为 CC 受欢迎,那么牛 AA 也认为牛 CC 受欢迎。

你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

输入格式

第一行两个数 n,mn, m。

接下来 mm 行,每行两个数 A,BA, B,意思是 AA 认为 BB 是受欢迎的(给出的信息有可能重复,即有可能出现多个相同的 (A,B)(A, B))。

输出格式

输出一个数,即有多少头牛被所有的牛认为是受欢迎的。

样例输入

3 3
1 2
2 1
2 3

样例输出

1

样例解释

牛 22 认为牛 33 受欢迎,牛 11 认为牛 22 受欢迎,由传递性牛 11 也认为牛 33 受欢迎,因此牛 33 被其余所有牛认为受欢迎。牛 11 与牛 22 都不被牛 33 认为受欢迎,所以答案为 11。

数据范围

对于 100%100\% 的数据:

  • n≤104n\le 10^4,m≤5×104m\le 5\times 10^4。

来源与许可

本题为 HAOI 2006 试题「受欢迎的牛」,题面与测试数据整理自 BZOJ 1051。

样例 1

输入

3 3
1 2
2 1
2 3

输出

1