Minimum Path Cover in a DAG

Given a directed acyclic graph (DAG) \(G=(V,E)\), a collection \(P\) of vertex-disjoint simple paths (i.e. paths whose vertices do not intersect) is called a path cover if every vertex in \(V\) appears in exactly one of the paths in \(P\). Note that each path in \(P\) can start from any vertex and can be of arbitrary length (in particular, a single vertex is considered a valid path of length 0).

The minimum path cover of \(G\) is a path cover with the fewest number of paths. Design an efficient algorithm to compute the minimum path cover of a given DAG.

Hint: The problem can be transformed into a maximum matching problem in a bipartite graph. In particular, for a DAG with \(n\) vertices, the minimum path cover size is \(n - M\), where \(M\) is the size of the maximum matching.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively. The vertices are labeled from 1 to \(n\). Each of the next \(m\) lines contains two integers \(u\) and \(v\) representing a directed edge from \(u\) to \(v\).

outputFormat

Output a single integer, the minimum number of paths required in a path cover of the DAG.

sample

3 2
1 2
2 3

1