| Codeforces Round 286 (Div. 2) |
|---|
| Закончено |
Королевство Шусеки — ведущая мировая нация в области инноваций и технологий. В королевстве есть n городов, пронумерованных от 1 до n.
Благодаря исследованию мистера Китаюты, наконец-то стало возможно сооружать телепортационные туннели между двумя городами. Телепортационный туннель соединяет два города в одном направлении, то есть, телепортационный туннель из города x в город y не может доставить из города y в город x. Можно последовательно путешествовать по нескольким туннелям, например, если построить туннель из города x в город y, а также туннель из города y в город z, то можно мгновенно путешествовать из города x в город z.
Мистер Китаюта также занимается национальной политикой. Он считает, что наличие транспорта между m парами городов (ai, bi) (1 ≤ i ≤ m) очень важно. Он планирует соорудить телепортационные туннели так, чтобы для каждой важной пары (ai, bi) было возможно пропутешествовать из города ai в город bi по одному или более телепортационным туннелям (при этом необязательно, чтобы из города bi можно было добраться в город ai). Найдите минимальное количество телепортационных туннелей, которые необходимо построить. Пока что между городами не построили ни одного телепортационного туннеля, а другого эффективного междугороднего транспорта нет.
В первой строке записано два целых числа через пробел, n и m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105), обозначающих количество городов в королевстве Шусеки и количество важных пар, соответственно.
В следующих m строках описаны важные пары. В i-й из них (1 ≤ i ≤ m) записано два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), обозначающих, что должно быть возможно путешествовать из города ai в город bi через один или более телепортационных туннелей. Гарантируется, что все пары (ai, bi) различны.
Выведите минимальное требуемое количество телепортационных туннелей для выполнения цели мистера Китаюты.
4 5
1 2
1 3
1 4
2 3
2 4
3
4 6
1 2
1 4
2 3
2 4
3 2
3 4
4
В первом примере один из оптимальных способов построить туннели показан на рисунке ниже:
Для второго примера один из оптимальных способов указан ниже:
