P2746 [IOI 1996 / USACO5.3] Network of Schools

Some schools share software with other schools; that is, if a school obtains the software, then all schools in its sharing list will also obtain the software. Note that this relation is directed: if $a$ is in $b$'s list, then $b$ is not necessarily in $a$'s list. Now you need to distribute new software to some of the schools. To minimize the distribution cost, answer the following two questions. 1. What is the minimum number of schools to which you must distribute the software so that all schools obtain the new software? 2. Define one expansion as adding one school to the sharing list of some school. What is the minimum number of expansions needed so that, no matter which single school you initially distribute the software to, all schools will obtain the new software? The two questions are independent.

The first line of input contains a positive integer $N$, the number of schools. The schools are numbered from $1$ to $N$. Each of the next $N$ lines describes a sharing list. Line $i+1$ lists the school IDs in the sharing list of school $i$. Each list is terminated by a $0$; an empty list is represented by a single $0$.

Output two lines. The first line should contain a positive integer, the answer to Question 1. The second line should contain a non-negative integer, the answer to Question 2.

Constraints: $2 \le N \le 100$. This translation is from NOCOW. Translated by ChatGPT 5