Cover graph vertices with non intersecting paths

Covering with paths

An oriented acyclic graph is given. Find the minimum number of disjoint paths covering all vertices.


First line contains number of vertices n and number of edges m (2n1000, 0m105). Each of the next m lines contains two numbers: the numbers of the vertces u and v connected with an edge (u, v).


Print the minimum number of paths that can cover all the vertices.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3 3
1 3
3 2
1 2
Output example #1
Author Антон Банных