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. На жодній з планет немає телепорту на саму себе. На жодній планеті немає двох телепортів на одну і ту ж планету.

Вихідні дані

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

prb1910.gif

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
6 4
3 1
4 6
1 2
4 5
Вихідні дані #1
2

Пояснення: Можна побудувати телепорт з планети 2 на планету 4 та з планети 5 на планету 3.

Автор Ельдар Богданов
Джерело Зимова Школа, Харків 2011, День 7