Королевство Шусеки — ведущая мировая нация в области инноваций и технологий. В королевстве есть 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). Найдите минимальное количество телепортационных туннелей, которые необходимо построить. Пока что между городами не построили ни одного телепортационного туннеля, а другого эффективного междугороднего транспорта нет.
Выходные данные
Выведите минимальное требуемое количество телепортационных туннелей для выполнения цели мистера Китаюты.
Примечание
В первом примере один из оптимальных способов построить туннели показан на рисунке ниже:
Для второго примера один из оптимальных способов указан ниже:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 2
1 3
1 4
2 3
2 4
|
3
|
|
2
|
4 6
1 2
1 4
2 3
2 4
3 2
3 4
|
4
|