Задачи
Количество путей
Количество путей
Дан ациклический ориенитрованный граф. Разбить граф на минимальное количество вершинно-непересекающихся путей. То есть каждая вершина должна принадлежать ровно одному пути.
Входные данные
Первая строка содержит количество вершин n и ребер k (1 ≤ n ≤ 500, 0 ≤ k ≤ n ·(n - 1) / 2) в графе. Следующие k строк содержат по два числа в каждой - a, b (1 ≤ a, b ≤ n), означающих наличие ребра из вершины a в вершину b. Каждая пара (a, b) встречается не более одного раза.
Выходные данные
Вывести минимальное количество путей.
Пример
Входные данные #1
7 6 1 4 2 4 3 4 4 5 4 6 4 7
Выходные данные #1
5