Disclosure

Задано ациклічний орієнтовний граф з N вершин та K ребер. Потрібно видалити з нього максимальну кількість ребер, щоб транзитивне замикання графа не змінилось.

Транзитивне замикання графа G - граф G', який складається з множини вершин заданого графа G і множини ребер (u, v) таких, що існує шлях з вершини u у вершину v у графі G.

Вхідні дані

У першому рядку два числа N і K. Далі K рядків, у кожному з яких по два цілих числа a_i та b_i, які позначають наявність ребра, яке веде з вершини a_i у b_i. Граф не містить петель, циклів і кратних ребер.

Вихідні дані

Вивести ті ребра, які необхідно залшти у графі, у вигляді пар з'єднаних ними вершин. Ребра можна виводити у довільному порядку.

Обмеження

1 ≤ N ≤ 50000

0 ≤ K ≤ 50000

1 ≤ a_i, b_i ≤ N

Приклади