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

Type: RemoteJudge

1000ms

128MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

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

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

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

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

2
2

~~POJ 原题。数据扩大了 $100$ 倍。~~

~~$1 \leq$ 边数 $\leq 5000000$ ， $1 \leq n \leq 10000$ 。~~

实际上， $1 \leq n \leq 10000$ ， $1\le$ 边数 $\le 50000$ 。