Hide and Seek in the Forest

Vani and cl2 are playing hide and seek in a forest. In this forest there are \(N\) houses and \(M\) directed roads forming a Directed Acyclic Graph (DAG). Because the trees are dense, one can only see along the roads. That is, if there exists a (directed) path from house \(A\) to house \(B\), then the occupants of houses \(A\) and \(B\) can see each other.

cl2 wants to choose a set of houses as hideouts such that any two chosen houses are not visible to each other (i.e. for any two hideouts there is no path from one to the other). In other words, the chosen set of houses must form an antichain in the DAG.

Using a famous theorem from poset theory, the maximum number of hideouts that may be selected is given by:

\( \text{Answer} = N - \text{(size of maximum matching)} \)

The problem is then to compute the size of the maximum antichain in the DAG.

inputFormat

The input begins with a line containing two integers \(N\) and \(M\) (1 ≤ N ≤ 10^5, 0 ≤ M ≤ 10^5) representing the number of houses and the number of directed roads, respectively.

Each of the next \(M\) lines contains two integers \(u\) and \(v\) (1 ≤ u, v \le; N) representing a directed road from house \(u\) to house \(v\). It is guaranteed that the directed graph is acyclic.

outputFormat

Output a single integer: the maximum number of hideouts cl2 can choose such that no two chosen houses are connected by a path.

sample

3 2
1 2
2 3

1