Disclosure#4596
You are given an acyclic directed graph with nodes and edges. Delete the maximum number of edges without changing the graph's transitive closure.
The transitive closure of a graph is a graph G', consisting of all nodes of the original graph and all edges such that there is a path from node to in .
The first line contains two integers and (1 \leq n \leq 50000, 0 \leq k \leq 50000). Each of the next lines contains two integers a_i and b_i (1 \leq a_i, b_i \leq n), describing a directed edge from a_i to b_i. The graph does not contain loops, cycles, or multiple edges.
Output all edges that must remain in the graph as pairs of connected nodes. The edges may be printed in any order.
Example 1