P10938 Vani and Cl2 Play Hide-and-Seek

Vani and cl2 are playing hide-and-seek in a forest. There are $N$ houses and $M$ directed roads in the forest, forming a directed acyclic graph. The trees in the forest are very dense and can block the line of sight, but along the roads the view is clear. If one can walk from house $A$ along the roads and reach $B$, then people in $A$ and $B$ can see each other. Now cl2 wants to choose $K$ of the $N$ houses as hiding places, and Vani will only enter the houses that cl2 chose to search. To avoid being seen by Vani, cl2 requires that for any two of these $K$ hiding places, there is no path connecting them. To make it harder for Vani to find him, cl2 wants to know the maximum number of hiding places that can be chosen.

The first line of the input contains two integers $N$ and $M$. The next $M$ lines each contain two integers $x,y$, indicating a directed road from $x$ to $y$.

Output one integer, the maximum number of hiding places that can be chosen.

- For $20\%$ of the testdata, $1\leq N\leq 10$, $1\leq M\leq 20$. - For $60\%$ of the testdata, $1\leq N\leq 100$, $1\leq M\leq 1000$. - For $100\%$ of the testdata, $1\leq N\leq 200$, $1\leq M\leq 30000$, $1\leq x,y\leq N$. Translated by ChatGPT 5