Problems
Covering with paths
Covering with paths
An oriented acyclic graph is given. Find the minimum number of disjoint paths covering all vertices.
Input
First line contains number of vertices n and number of edges m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 105
). Each of the next m lines contains two numbers: the numbers of the vertces u and v connected with an edge (u, v).
Output
Print the minimum number of paths that can cover all the vertices.
Input example #1
3 3 1 3 3 2 1 2
Output example #1
1