eolymp
bolt
Try our new interface for solving problems
Problems

The Bottom of a Graph

The Bottom of a Graph

\includegraphics{https://static.e-olymp.com/content/17/17036a020b88689c250b155e7cf491dca420724a.jpg} We will use the following (standard) definitions from graph theory. Let \textbf{V} be a nonempty and finite set, its elements being called \textit{vertices} (or nodes). Let \textbf{E} \textbf{V}×\textbf{V} , its elements being called \textit{edges}. Then \textbf{G = (V,E)} is called a \textit{directed graph}. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Let \textbf{n} be a positive integer, and let \textbf{p = (e_1, ..., e_n)} be a sequence of length \textbf{n} of edges \textbf{e_i} \textbf{E} such that \textbf{e_i = (v_i, v_\{i+1\})} for a sequence of vertices \textbf{(v_1, ..., v_\{n+1\})}. Then \textbf{p} is called a \textit{path} from vertex \textbf{v_1} to vertex \textbf{v_\{n+1\}} in \textbf{G} and we say that \textbf{v_\{n+1\}} is reachable from \textbf{v_1}, writing \textbf{(v_1 }→\textbf{ v_\{n+1\})}. Here are some new definitions. A node \textbf{v} in a graph \textbf{G = (V, E)} is called a \textit{sink}, if for every node \textbf{w} in \textbf{G} that is reachable from \textbf{v}, \textbf{v} is also reachable from \textbf{w}. The bottom of a graph is the subset of all nodes that are sinks, i.e., \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a9/a95e3a2fa6a4bb21891b266af71619da5c09face.jpg} \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} \includegraphics{https://static.e-olymp.com/content/a9/a957158fbf72e5ef51a877838ff816e405ad1109.jpg} \textbf{bottom(G) = \{v V | (w V )v }→\textbf{ w w }→\textbf{ v\}}. Your task is to calculate the bottom of certain graphs. \InputFile \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} The input contains several test cases, each of which corresponds to a directed graph \textbf{G}. Each test case starts with an integer number \textbf{v}, denoting the number of vertices of \textbf{G = (V, E)}, where the vertices will be identified by the integer numbers in the set \textbf{V = \{1, ..., v\}}. You may assume that \textbf{1} ≤ \textbf{v} ≤ \textbf{5000}. That is followed by a non-negative integer \textbf{e}and then \textbf{e} pairs of vertex identifiers \textbf{v_1, w_1, ..., v_e, w_e} with the meaning that \textbf{(v_i, w_i)} \textbf{E}. There are no edges other than specified by these pairs. The last test case is followed by a zero. \OutputFile 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.
Time limit 1 second
Memory limit 64 MiB
Input example #1
3 3
1 3 2 3 3 1
2 1
1 2
0
Output example #1
1 3
2