Description

There are $n$ cities connected by one-way roads. Messages spread along the roads. Given $n$ cities and the roads between them, ask for the minimum number of cities where you need to initially publish the message so that all $n$ cities receive it.

Input Format

The first line contains two integers $n, m$, meaning $n$ cities and $m$ directed roads. In the next $m$ lines, each line contains two integers $b, e$, indicating there is a road from $b$ to $e$. Multiple edges and self-loops are allowed.

Output Format

Output a single integer, the minimum number of cities where the message must be published.

5 4
1 2
2 1
2 3
5 1

2

Hint

• Sample Explanation #1
  In the sample, publish the message in cities $4$ and $5$.

• Constraints
  For $20\%$ of the testdata, $n \le 200$.
  For $40\%$ of the testdata, $n \le 2000$.
  For $100\%$ of the testdata, $1 \le n \le {10}^5$, $1 \le m \le 5 \times {10}^5$.

Translated by ChatGPT 5