logo AlgoBeat OnlineJudge
登录 注册

#10039. 奶牛的总攻

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

题目描述

奶牛们即将对小信发起总攻,可他们不知道要听谁的指挥。

奶牛推举领导奶牛的方式非常简单,每头奶牛说出自己信任哪些奶牛。如果某头奶牛被除了自己以外的其他所有奶牛直接或间接的信任了,这头奶牛就可以成为领导奶牛。如果其他所有奶牛信任都不信任某头奶牛,这头奶牛就被称为可疑奶牛,其不能参与战斗。

例如,如果奶牛 X 信任 Y,Y 信任 Z,那么 X 直接的信任了 Y,间接的信任了 Z,Y 直接或间接信任的人将被 X 间接信任。这种推举方式会使得奶牛们可能会产生多个领导人,这也是能被奶牛接受的。

输入格式

第一行:两个用空格分开的整数:,表示有 头奶牛(编号为 ),有 个信任关系。

接下来 行,每行读入 个整数 ,表示 直接信任

输出格式

两个整数,分别代表推举出的领导奶牛的头数和能参与战斗的奶牛头数。

样例

输入 #1

3 3
1 2
2 3
1 3

输出 #1

1 2

输入 #2

3 2
1 2
2 1

输出 #2

0 2

输入 #3

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

输出 #3

3 6

数据范围与提示

出题人:cje130725
验题人:???
数据人:cje130725
使