Дан ациклический ориентированный граф из n вершин и k рёбер. Требуется удалить из него максимальное количество рёбер, чтобы транзитивное замыкание графа не изменилось.
Транзитивное замыкание графа G - граф G', состоящий из множества вершин исходного графа G и множества рёбер (u, v) таких, что существует путь из вершины u в вершину v в графе G.
В первой строке находятся два числа n и k (1 ≤ n ≤ 50000, 0 ≤ k ≤ 50000). Далее k строк, в каждой из которых по два целых числа a_i и b_i, означающих наличие ребра, ведущего из вершины a_i в b_i (1 ≤ a_i, b_{i }≤ n). Граф не содержит петель, циклов и кратных рёбер.
Вывести те рёбра, которые необходимо оставить в графе, в виде пар соединенных ими вершин. Рёбра можно выводить в любом порядке.