## BOTTOM - The Bottom of a Graph

no tags

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 \times 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_1, \ldots, e_n)$ be a sequence of length $n$ 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 $p$ is called a path from vertex $v_1$ to vertex $v_{n+1}$ in $G$ 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 $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., $\mathrm{bottom}(G) = \{v \in V \mid \forall w \in V : (v \to w) \Rightarrow (w \to v) \}$. You have to calculate the bottom of certain graphs.

### Input Specification

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, \ldots, v\}$. You may assume that $1 \le v \le 5000$. That is followed by a non-negative integer $e$ and, thereafter, $e$ 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.

### Output Specification

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 Ankit Kumar: 2015-07-16 21:07:13 O(V+E) solution -> AC Best DFS prob solved by me on SPOJ till now :) i_am_looser: 2015-06-06 21:27:19 Good question..... learnt something useful Arafat dad Khan: 2015-06-03 17:57:47 Great problem for learning new things Arya08: 2015-05-29 20:39:00 best dfs problem. solved by me(till now ) ehacker: 2015-05-26 22:53:03 My testcases are correct even the ones which are mentioned in the comments, don't know, i am using a do while loop and output the value as i calculated for that case???? ayush nigam: 2015-03-17 10:22:02 Last edit: 2015-03-17 10:23:32 eli: 2015-03-11 16:18:36 2 can't reach 1 so it works. Archit Jain: 2014-12-26 20:13:55 seems easy but difficult to implement |RAMSDEN|: 2014-12-25 21:09:22 A silly mistake costed me many WAs :p ankipanki: 2014-12-07 00:22:06 Those who are getting wrong answer, Input: 4 1 1 2 0 output: 2 3 4