Cycle Breaking in Directed Graphs

Mike Micromanager is responsible for maintaining the city street network. However, the network contains several cycles which may lead to traffic congestions. Your task is to identify a set of directed edges whose removal will break all cycles in the graph. For each strongly connected component (SCC) with more than one node, you need to remove exactly one edge such that the remaining network is as connected as possible.

The problem can be formulated as follows. You are given \( n \) intersections and \( m \) directed roads. The intersections are numbered from 1 to \( n \). Each road is represented by a directed edge \( (u,v) \) indicating a one-way street from intersection \( u \) to intersection \( v \). Your task is to choose a set of edges (one from each non-trivial SCC) to remove in order to break all cycles in the network.

Note: If there is no cycle in the network, no edge should be removed.

inputFormat

The first line of input contains two integers \( n \) and \( m \) where \( n \) is the number of intersections and \( m \) is the number of directed edges.

The next \( m \) lines each contain two integers \( u \) and \( v \), representing a directed edge from \( u \) to \( v \).

outputFormat

Output the edges to be removed, one per line. Each line should contain two integers \( u \) and \( v \) separated by a space. The edges must be output in increasing order (sorted by \( u \) first, then by \( v \)). If no edge needs to be removed, output nothing.

## sample

6 9
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6

1 2
4 5

</p>