Виявлення#4596
Вам дано ациклічний орієнтований граф із вершинами та ребрами. Видаліть максимальну кількість ребер так, щоб транзитивне замикання графа не змінилося.
Транзитивне замикання графа — це граф G', що складається з усіх вершин оригінального графа та всіх ребер , таких, що існує шлях із вершини до вершини у .
У першому рядку знаходяться два цілих числа та (1 \leq n \leq 50000, 0 \leq k \leq 50000). Кожен із наступних рядків містить по два цілих числа a_i та b_i (1 \leq a_i, b_i \leq n), що описують орієнтоване ребро з a_i у b_i. Граф не містить петель, циклів чи кратних ребер.
Виведіть усі ребра, які обов'язково мають залишитися у графі, у вигляді пар з'єднаних вершин. Порядок ребер у відповіді довільний.
Приклад 1