e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

Strong Connected Components

Империя

Империя включает в себя n планет. Пронумеруем эти планеты числами от 1 до n. Планета с номером 1 - столица Империи, где находится резиденция Императора и подготавливаются войска. На различных планетах империи часто вспыхивают восстания, которые приходится подавлять военной силой и немедленно.

Для того чтобы войска могли быстро передвигаться, на некоторых планетах установлены односторонние телепорты. Всего телепортов m штук. С помощью i-ого телепорта можно в мгновение ока попасть с планеты ai на планету bi (но не наоборот). Таким образом, вовремя подавить восстание на некоторой планете x можно, если существует последовательность планет p1, ..., pk (k2) такая, что p1 = 1, pk = x, а для каждого 1i < k есть телепорт из планеты с номером pi на планету с номером pi+1. Учитывая, что после подавления восстания войска остаются на планете для поддержания порядка, об их возвращении в столицу мы можем не беспокоиться.

Проверьте, есть ли возможность при имеющихся телепортах подавить восстание на любой планете Империи. Если это так, то выведите 0. В противном случае, найдите наименьшее количество телепортов, которое надо дополнительно построить, чтобы восстание на любой планете было подавляемо. Каждый телепорт может быть построен между произвольными двумя планетами.

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

Первая строка содержит два целых числа n и m (2n105, 0m2·105). i-ая из следующих m строк содержит пару чисел ai, bi (1ai, bin) для всех 1im. Ни на одной планете нет телепорта в саму себя. Ни на одной планете нет двух телепортов на одну и ту же планету.

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

Выведите наименьшее количество телепортов, гарантирующее, что восстание на любой планете можно будет немедленно подавить.

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #1
6 4
3 1
4 6
1 2
4 5
Выходные данные #1
2

Объяснение: Можно построить телепорт из планеты 2 на планету 4 и из планеты 5 на планету 3.

Автор Эльдар Богданов
Источник Зимняя школа, Харьков 2011, День 7