#6197. 法克

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AntiLeaf

题目描述

n 个英雄想打一盘游戏。但是游戏终归是游戏,由于这个游戏的某些坑爹设定,某些英雄之间会有一些压制关系。

具体来说,我们会给出 m 个压制关系,表示英雄 a 直接压制英雄 b 。注意压制关系是有传递性的,也就是说如果存在一个三元组 (a,b,c) 满足 a 压制 b b 压制 c ,那么 a 也压制 c 。同时由于游戏的某些设定,压制关系不会出现环,也就是说不会出现一个英雄直接或间接压制自己的情况(我们称 a 间接压制 b 当且仅当 a 可以压制 b 但不直接压制 b )。

显然英雄之间的压制关系是很影响打游戏的乐趣的(如果你被某个同样在打游戏的英雄压制,那对你来说这盘游戏很可能会很没意思),因此英雄们希望打游戏的英雄之间互相不压制。为了达到这个目的,英雄们决定只选出一部分英雄打游戏,剩下的英雄下一盘再说。显然选出的英雄们越多英雄们就会越高兴。

不过,英雄们战斗力个个都很强,但智力相对来说还是差了点。所以英雄们找到了你,请你为他们帮忙。如果你能在 \text{1 s} 内算出最多能选出几个英雄去打游戏,他们会很乐意让你也加入这盘游戏(显然你这种凡人是不会和英雄们产生压制关系的)。

输入格式

第一行两个正整数 n,m ,分别表示英雄人数和直接压制关系的数目。
以下 m 行,每行两个 [1,n] 内的整数 a,b ,表示英雄 a 直接压制英雄 b

输出格式

一行一个整数表示答案。

样例

样例输入

5 5
1 2
2 3
2 4
2 5
4 5

样例输出

2

样例解释

一种选出 2 个英雄的方案是选择英雄 3,5

数据范围与提示

本题共有 10 个测试点,每个测试点的分值均为 10 分。
对于 30\% 的数据, n\le 18
对于 50\% 的数据, n\le 10^3
另有 30\% 的数据,每个英雄最多只被一个英雄直接压制;
对于 100\% 的数据, n\le 10^5 m\le 2n

题解&标程