Problems
Количество путей
Количество путей
The oriented graph without cycles is given. Разбить граф на минимальное количество вершинно-непересекающихся путей. То есть каждая вершина должна принадлежать ровно одному пути.
Input
The first line contains the number of vertices n and edges k (1 ≤ n ≤ 500, 0 ≤ k ≤ n ·(n - 1) / 2) in the graph. Each of the next k lines contains two integers - a, b (1 ≤ a, b ≤ n), giving the description of an edge from vertex a to vertex b. Each pair (a, b) appears no more than one time.
Output
Print the minimal possible number of paths.
Input example #1
7 6 1 4 2 4 3 4 4 5 4 6 4 7
Output example #1
5