eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Покрытие путями

Покрытие путями

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задан ориентированный ациклический граф. Определить минимальное количество непересекающихся путей, покрывающих все вершины.

Входные данные

Первая строка содержит количество вершин n и количество m ребер графа соответственно (2n1000, 0m10^5). В следующих m строках содержатся по два числа: номера вершин u и v, которые соединяет ребро (u, v).

Выходные данные

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

Пример

Входные данные #1
3 3
1 3
3 2
1 2
Выходные данные #1
1
Автор Антон Банных