P2812 Campus Network [USACO] Network of Schools Enhanced Version

Several OI powerhouse schools in Zhejiang have shen niu (pinyin: shén niú) who invented an artificial intelligence that can AC any problem, so they decided to build a network to share this software. However, due to excessive brainwork, they are completely drained and have come to you for help.

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.

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$.

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.

~~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