Sacred Ceremonies of the Y Tribe

In the mysterious Far East, there exists an enigmatic tribe known as the Y Tribe. They have lived for generations on water, worshiping the Dragon King as their deity. During grand celebrations, the Y Tribe holds majestic ceremonies on various junctions in their water network. The water network is composed of junctions (forks) and directed river channels. Each channel connects two junctions and the water flows in a fixed direction along it. Since there are no cycles in the water system, if water flows from one ceremony site to another, that ceremony would lose its sacred significance.

The tribe’s chieftain wishes to select as many sites as possible for the ceremonies, while ensuring that for any two chosen sites, there is no path along which water can flow from one to the other. In other words, if we view the water system as a directed acyclic graph (DAG), we must choose a maximum set of nodes such that no node in the set is reachable from another. This maximum antichain problem has an interesting theoretical result: by Dilworth's Theorem, its size equals the number of nodes minus the size of the maximum matching in a related bipartite graph. Formally, if there are n junctions and the size of the maximum matching is M, then the maximum number of valid ceremony sites is given by

$$\text{Answer} = n - M$$

Your task is to compute this number for a given water network.

inputFormat

The first line contains two integers n and m, representing the number of junctions and the number of directed river channels respectively. Each of the following m lines contains two integers u and v, indicating a river flowing from junction u to junction v.

outputFormat

Output a single integer, the maximum number of sacred ceremony locations, i.e. the size of the maximum antichain.

sample

3 2
1 2
2 3

1