The Bottom of a Graph#6223
We will use the following (standard) definitions from graph theory. Let be a nonempty finite set, its elements being called vertices (or nodes). Let E\subseteq V\times V, its elements being called edges. Then G = (V, E) is called a directed graph.
Let be a positive integer, and let p = (e_1, \ldots, e_n) be a sequence of length of edges e_i \in E such that e_i = (v_i, v_{i+1}) for a sequence of vertices (v_1, \ldots, v_{n+1}). Then is called a path from vertex v_1 to vertex v_{n+1} in , and we say that v_{n+1} is reachable from v_1, writing (v_1 \to v_{n+1}).
Here are some new definitions. A node in a graph G = (V, E) is called a sink if, for every node in that is reachable from , is also reachable from .
The bottom of a graph is the subset of all nodes that are sinks, i.e.,
Your task is to calculate the bottom of certain graphs.
The input contains several test cases, each of which corresponds to a directed graph . Each test case starts with an integer , denoting the number of vertices of G = (V, E), where the vertices are identified by the integer numbers in the set V = \{1, \ldots, v\}. You may assume that 1 \le v \le 5000. This is followed by a non-negative integer , then pairs of vertex identifiers v_1, w_1, \ldots, v_e, w_e with the meaning that (v_i, w_i) \in E. There are no edges other than specified by these pairs. The last test case is followed by a zero.
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.
Example 1