EduBrick

L. Авиалинии

3000 мс · 256 МБ · всё или ничего

Дан ориентированный граф рейсов. Составьте новый план с наименьшим числом рейсов так, чтобы достижимость между городами не изменилась: если из aa можно было долететь до bb (возможно, с пересадками), то и в новом плане можно, и наоборот. Новые рейсы разрешено проводить между любыми парами городов.

Выведите только количество рейсов в наименьшем плане.

Формат ввода

Первая строка содержит числа NN (1≤N≤1031 \le N \le 10^3) и MM (0≤M≤1040 \le M \le 10^4).

Далее идут MM строк с рейсами. Возможны кратные рейсы; петель нет.

Формат вывода

Одно число — наименьшее возможное количество рейсов.

Примеры

ввод
4 5
1 2
2 3
2 1
3 2
2 4
вывод
4
ввод
3 3
1 2
2 3
1 3
вывод
2
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.