Maximal Removable Edge Set

Given a directed graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges, find a maximal subset \(R \subseteq E\) such that if all edges in \(R\) are removed the reachability between vertices is preserved. In other words, for any two vertices \(u,v\) where there is a path from \(u\) to \(v\) in \(G\), there must also be a path from \(u\) to \(v\) in the graph \(G'=(V,E\setminus R)\).

A greedy approach that tries to remove edges one by one while testing the property is acceptable. Note that although an edge might be redundant when considered individually, removing many redundant edges simultaneously might break the connectivity if the redundancy is mutual. Hence, one must choose a set \(R\) so that the graph \(G'=(V,E\setminus R)\) preserves the original reachability relation.

Hint: Let the original connectivity relation of \(G\) be represented using a boolean matrix computed by the Floyd–Warshall algorithm. Then, try removing each edge (in input order) from the current graph and recompute the transitive closure. If for every pair \((u,v)\) with a path in \(G\) there still exists a path in the new graph, then the removal is safe. Continue this greedily.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the number of vertices and edges respectively. Vertices are numbered from \(1\) to \(n\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) representing a directed edge from vertex \(u\) to vertex \(v\).

outputFormat

On the first line, output an integer \(k\), the number of edges in the maximal removable set \(R\). Then output \(k\) lines, each containing two integers \(u\) and \(v\) representing a removable edge.

sample

3 3
1 2
2 3
3 1

0