Disclosure

You are given an acyclic directed graph, consisting of n nodes and k edges. Delete maximum amount of edges, without causing graph's transitive closure to change.

Transitive closure of graph G is a graph G', consisting of all nodes of orgignal graph G and such edges (u, v) that there is a path from node u to v in graph G.

Input

The first line contains two numbers n and k (1 ≤ n ≤ 50000, 0 ≤ k ≤ 50000). Then k lines follow, each containing two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), descripting directed edge from a_i to b_i. Graph doesn't contain loops, cycles and multiple edges.

Output

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.

Examples