Problems
Disclosure
Disclosure
You are given an acyclic directed graph, consisting of \textbf{n }nodes and \textbf{k }edges. Delete maximum amount of edges, without causing graph's transitive closure to change.
Transitive closure of graph \textbf{G} is a graph \textbf{G'}, consisting of all nodes of orgignal graph \textbf{G }and such edges (\textbf{u}, \textbf{v}) that there is a path from node \textbf{u }to \textbf{v }in graph \textbf{G}.
\InputFile
The first line contains two numbers \textbf{n }and \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{50000}, \textbf{0} ≤ \textbf{k} ≤ \textbf{50000}). Then \textbf{k }lines follow, each containing two integers \textbf{a_i} and \textbf{b_i} (\textbf{1} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{n}), descripting directed edge from \textbf{a_i} to \textbf{b_i}. Graph doesn't contain loops, cycles and multiple edges.
\OutputFile
Output the every edge that is necessary to remain in graph as the pair of nodes connected by this edge. Edges can be written in any order.
Input example #1
5 6 1 2 2 3 3 5 4 5 1 5 1 3
Output example #1
1 2 2 3 3 5 4 5