Network of Schools

A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.

Input

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

Output

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

Sample Input

5
2 4 3 0
4 5 0
0
0
1 0

Sample Output

12

Source

IOI 1996

题目类型：有向图强连通分量+缩点

算法分析：易知同一个强连通分量A中的学校之间可以相互拷贝软件，若外部一个点a和A中的点b相连，则a处的软件可以传遍A。反之若A中的点a和外部的一个点b相连，则b和A中所有的点相连，所以可以缩点。最后答案a的结果是缩点后出度为0的顶点个数。之后为了能够将缩点后的图填最少的边构建成一个强连通图，易知需要在出度为0的点和入度为0的点之间连边。直到所有出度为0的点和入度为0的点都没有为止。这样答案b的结果就是出度为0的点个数和入度为0的点个数之间的较大值。注意：当缩点后只有一个点时，需要特判输出0！！！

The Bottom of a Graph

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges. Then G=(V,E) is called a directed graph.
Let n be a positive integer, and let p=(e₁,...,e_n) be a sequence of length n of edges e_i∈E such that e_i=(v_i,v_i+1) for a sequence of vertices (v₁,...,v_n+1). Then p is called a path from vertex v₁ to vertex v_n+1 in G and we say that v_n+1 is reachable from v₁, writing (v₁→v_n+1).
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from v, v is also reachable from w. The bottom of a graph is the subset of all nodes that are sinks, i.e., bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v₁,w₁,...,v_e,w_e with the meaning that (v_i,w_i)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output

1 3

2

Source

Ulm Local 2003

题目类型：有向图强连通分量(Tarjan)+缩点

算法分析：本题要找所有满足”能够到达其他顶点w(w != u)的点u是否能够从w点到达”的所有的u点，即不考察那些u不可达的点的情况。由于同一个强连通分量中的顶点都是双向可达的，所以其中任意一个点对于同一个强连通分量中的其它点都是满足条件的，可以缩点。易知缩点后得到的图中出度为0的缩点都满足条件