Problem1091--「一本通 3.5 例 1」受欢迎的牛

1091: 「一本通 3.5 例 1」受欢迎的牛

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:USACO 2003 Fall

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 NNN 头牛,给你 MMM 对整数 (A,B)(A,B)(A,B),表示牛 AAA 认为牛 BBB 受欢迎。这种关系是具有传递性的,如果 AAA 认为 BBB 受欢迎,BBB 认为 CCC 受欢迎,那么牛 AAA 也认为牛 CCC 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。


Input

第一行两个数 N,MN,MN,M
接下来 MMM 行,每行两个数 A,BA,BA,B,意思是 AAA 认为 BBB 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A,BA,BA,B)。


Output

输出被除自己之外的所有牛认为是受欢迎的牛的数量。


Sample Input

3 3
1 2
2 1
2 3

Sample Output

1

HINT

对于全部数据,1≤N≤104,1≤M≤5×1041\le N\le 10^4,1\le M\le 5\times 10^41N104,1M5×104


Source/Category


Submit Status