Cake delivery

Time limit1sMemory limit64 MB

Summary

Given a directed graph where every village must be reachable from village 1, find the minimum number of walks starting at village 1 that together cover all vertices.

Level: Medium7 of 10
Topics: Graph, Dynamic programming, Greedy, Shortest path
Solved: No attempts yet

Problem

Mirko makes the best cake in his village, a grapefruit cheesecake. To advertise the recipe he decided to give at least one cake to each of the $N$ villages in his county. He hires several traveling salesmen for the job. A salesman carries as many cakes as he wants and hands them out while moving along the one way roads that connect the villages.

Every salesman starts in Mirko's village, which is village 1. Mirko picks the route of every salesman he hires. A route is any sequence of roads joined end to end, and it may pass through the same village more than once. A salesman is allowed to stay put, and such a salesman delivers only to village 1.

What is the smallest number of salesmen Mirko has to hire so that every village gets a cake?

Input

The first line contains the number of villages $N$ and the number of roads $E$ ( $1 \le N \le 500$ , $1 \le E \le 50000$ ).

Each of the next $E$ lines contains two integers $A$ and $B$ ( $1 \le A, B \le N$ ). This means there is a one way road from village $A$ to village $B$ , so a salesman can go directly from village $A$ to village $B$ .

The same road may be given more than once, and $A$ and $B$ may be equal.

Output

Print the smallest number of salesmen Mirko has to hire. The input is always such that a way to give every village a cake exists.

Examples3

Example 1
Input
```
3 4
1 2
1 2
2 3
2 3
```
Expected output
```
1
```
Example 2
Input
```
4 4
1 2
1 3
2 4
3 4
```
Expected output
```
2
```
Example 3
Input
```
4 5
1 2
1 3
2 4
3 4
4 1
```
Expected output
```
1
```