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

Количество путей

Количество путей

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

Дан ациклический ориенитрованный граф. Разбить граф на минимальное количество вершинно-непересекающихся путей. То есть каждая вершина должна принадлежать ровно одному пути.

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

Первая строка содержит количество вершин n и ребер k (1n500, 0kn ·(n - 1) / 2) в графе. Следующие k строк содержат по два числа в каждой - a, b (1a, bn), означающих наличие ребра из вершины a в вершину b. Каждая пара (a, b) встречается не более одного раза.

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

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

Пример

Входные данные #1
7 6
1 4
2 4
3 4
4 5
4 6
4 7
Выходные данные #1
5
Источник III Международная Летняя школа программирования 2012 г. Севастополь