3437 - 校园网络

题目描述

浙江省的几所 OI 强校的神犇发明了一种人工智能,可以 AC 任何题目,所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被掏空,他们来找你帮助他们。

共有 n 所学校 (1≤n≤10000) 已知他们实现设计好的网络共 m 条线路,为了保证高速,网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机,能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

输入

第一行一个正整数 n。

接下来 n 行每行有若干个整数,用空格隔开。

第 i+1 行,每行输入若干个非零整数 x,表示从 i 到 x 有一条线路。以 0 作为结束标志。

输出

第一行一个整数,表示至少选几所学校作为共享软件的母机,能使每所学校都可以用上。

第二行一个整数,表示至少要添加几条线路能使任意一所学校作为母机都可以使别的学校使用上软件。

样例

输入

5
2 0
4 0
5 0
1 0
0

输出

2
2
说明

【数据范围】

1≤n≤10000,1≤ 边数 ≤50000。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 4 枚
难度 提高


上一题 下一题