eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Конденсация графа

Конденсация графа

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

Для заданного ориентированного графа найти количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G', вершинами которого служат компоненты сильной связности G, а дуга в G' присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

Входные данные

Первая строка содержит количество вершин n и количество ребер m (n10^4*, m10^5) графа. Каждая из следующих m строк содержит описание ребра графа. i-ое ребро описывается номерами начальной b[i] и конечной e[i] (1b[i], e[i]n) вершины. В графе могут присутствовать кратные ребра и петли.

Выходные данные

Выведите количество ребер в конденсации графа.

prb1947.gif

Пример

Входные данные #1
4 4
2 1
3 2
2 3
4 3
Выходные данные #1
2
Автор Виталий Гольдштейн
Источник Зимняя школа, Харьков 2011, День 9