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

Strong Connected Components

Доміно

З доміно мажна придумувати різні забави. Діти люблять будувати домно в лінію, ставлячи їх рядом один з одним. Якщо одне доміно адає, то воно вдаряє доміно, що стоїть поруч, а те в свою чергу падає на наступне і так далі продовжується процес падіння. Проте можуть існувати такі розміщення, що не всі доміно впадуть. В такому випадку необхідно рукою штовхнути ще одне доміно і падіння доміно продовжиться.

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

Вхідні дані

Перший рядок містить два числа, кожне з яких не більше за 105. Перше число - це кількість костей доміно n, а друге – кількість рядків m, які йдуть далі. Кості доміно пронумеровано числами від 1 до n. Кожен з наступних рядків містить два числа x та y, які означають, що якщо доміно x впаде, то воно зіб’є доміно y.

Вихідні дані

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

prb1104.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 2
1 2
2 3
Вихідні дані #1
1
Вхідні дані #2
5 5
2 3
1 2
4 2
5 3
5 4
Вихідні дані #2
2
Джерело Літня Школа 2010, Севастополь, день М.Медвєдева