校园网络【[USACO]Network of Schools加强版】

题目背景

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

题目描述

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

输入输出格式

输入格式


第一行一个整数n。 接下来n行每行有若干个整数,用空格空格隔开。 第i-1行的非零整数x,表示从i到x有一条线路。以0作为结束标志。

输出格式


第一行一个整数表示问题1的答案。 第二行回答问题2.

输入输出样例

输入样例 #1

5
2 0
4 0
5 0
1 0
0

输出样例 #1

2
2

说明

POJ原题。数据扩大了100倍。 边数 $\leq5000000$