Minimum Chain Cover

In a graph, a chain is a sequence of vertices in which every pair of neighbouring vertices is joined by an edge. The same vertex may appear more than once, and a single vertex is already a chain.

You are given a directed graph with no cycles. Find the smallest number of chains needed to cover every vertex.

Two different chains may not share a vertex. A sequence $v_1, v_2, \dots, v_k$ is a chain only if there is an edge from $v_i$ to $v_{i+1}$ for every $i$, so edges cannot be traversed against their direction.

The first line contains the number of vertices $N$ ($1 \le N \le 10000$) and the number of edges $M$ ($0 \le M \le 100000$). The vertices are numbered from $1$ to $N$.

Each of the next $M$ lines contains two integers $u$ and $v$, meaning there is an edge from $u$ to $v$. The same edge may be given more than once.

The given graph contains no cycle.

Print the minimum number of chains needed to cover every vertex, on one line.

The first example is covered by the two chains $2 \to 7 \to 3 \to 6$ and $1 \to 5 \to 4$, which together hold all seven vertices.