校园网络加强版(School Network Enhanced)

题目描述

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

共有 $n$ 所学校（$1 \leq n \leq 10^4$）。已知他们设计好的网络共 $m$ 条有向线路。若某所学校获得了软件，则它可以沿着这些有向线路将软件传播给后继学校。

现在需要你解决两个问题：

1. 最少需要选择多少所学校作为初始种子（即一开始就拥有该软件的学校），才能保证通过有向线路的传播，最终所有学校都能获得该软件？
2. 最少需要新增多少条有向线路，才能使得从任意一所学校出发，都能通过传播使所有学校都获得该软件？

输入格式

第一行一个正整数 $n$。

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

第 $i+1$ 行，每行输若干整数 $x_i$，表示从 $i$ 到 $x_i$ 有一条有向线路。每行以 $0$ 作为该行结束标志。

输出格式

第一行一个整数，表示问题 1 的答案。

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

样例输入 #1

5
2 0
4 0
5 0
1 0
0

样例输出 #1

2
2

数据范围

对于所有数据，有 $1 \leq n \leq 10^4$，$1\le m \le 5 \times 10^4$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接