Задачи
Покрытие путями
Покрытие путями
Задан ориентированный ациклический граф. Определить минимальное количество непересекающихся путей, покрывающих все вершины.
Входные данные
Первая строка содержит количество вершин n и количество m ребер графа соответственно (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10^5
). В следующих m строках содержатся по два числа: номера вершин u и v, которые соединяет ребро (u, v).
Выходные данные
Выведите минимальное количество путей, которыми можно покрыть все вершины.
Пример
Входные данные #1
3 3 1 3 3 2 1 2
Выходные данные #1
1