Description

There are $n$ schools ($1 \leq n \leq 10000$). It is known that in their designed network there are $m$ edges. To ensure high speed, the network is directed. Please tell them the minimum number of schools to select as servers (“mother machines”) so that every school can use the software. Then tell them the minimum number of edges to add so that choosing any single school as the server will allow every other school to use the software.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain several integers separated by spaces.

On the $(i+1)$-th line, several non-zero integers $x$ are given, indicating that there is a directed edge from $i$ to $x$. The line ends with a terminating $0$.

Output Format

The first line contains an integer, the minimum number of schools to select as servers so that every school can use the software.

The second line contains an integer, the minimum number of edges to add so that choosing any school as the server will allow every other school to use the software.

5
2 0
4 0
5 0
1 0
0

2
2

Hint

POJ original. The testdata has been enlarged by $100$ times.

$1 \leq n \leq 10000$, $1 \leq m \leq 5000000$.

In fact, $1 \leq n \leq 10000$, $1 \leq m \leq 50000$.

Translated by ChatGPT 5