- Time limit: 1.00 s
- Memory limit: 512 MB
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?
Input
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$.
Output
You should output one integer: the minimum number of days.
Example
Input:
6 7
2 1
2 5
3 2
5 1
5 4
6 2
6 3
Output:
3
Subtask 1 (16 points)
- $1 \le n \le 10$
- $1 \le m \le 20$
- $1 \le n \le 100$
- $1 \le m \le 200$
- $1 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$