CSES - Datatähti Open 2017 - Tunnels
  • Time limit: 1.00 s
  • Memory limit: 512 MB
You are playing a game that consists of $n$ rooms and $m$ tunnels. Each tunnel can be walked in one direction only, and there is no path from any room to itself through tunnels.

Each tunnel contains coins, and your task is to collect them. You can collect the coins in a tunnel by walking through the tunnel. However, due to a curse, the tunnel will be destroyed after this and you can't walk again through it.

The game consists of days, and at the beginning of each day you can start at any room and then move to other rooms through tunnels. What is the smallest number of days needed to collect all the coins?


The first input line contains two integers $n$ and $m$: the number of rooms and tunnels. The rooms are numbered $1,2\ldots,n$.

After this, the input contains $m$ lines, each of them having two integers $a$ and $b$. This means that there is a tunnel from room $a$ to room $b$.


You should output one integer: the minimum number of days.


6 7
2 1
2 5
3 2
5 1
5 4
6 2
6 3


Subtask 1 (16 points)
  • $1 \le n \le 10$
  • $1 \le m \le 20$
Subtask 2 (31 points)
  • $1 \le n \le 100$
  • $1 \le m \le 200$
Subtask 3 (53 points)
  • $1 \le n \le 10^5$
  • $1 \le m \le 2 \cdot 10^5$