A Water Slide at Catholic University??

Interview

Time limit1sMemory limit1024 MB

Summary

Given a directed graph, find the minimum number of starting vertices whose reachable sets cover every vertex.

Level: Medium6 of 10
Topics: Graph, BFS, DFS, Greedy
Solved: No attempts yet

Problem

Chisam is building a water slide at Catholic University that carries water from one building rooftop to another to celebrate the festival!

The university has N buildings, numbered 1 through N for convenience. Tunnels connect pairs of rooftops. If a tunnel is installed between two rooftops, water flows along it to the connected rooftop. Each tunnel has a fixed direction, so water can only flow the given way, and it flows to every reachable rooftop. For example, if there is a tunnel from 1 to 2 and another from 2 to 3, pouring water on building 1 sends water to the rooftops of buildings 2 and 3 as well. There can be several tunnels between two rooftops, but no tunnel connects a rooftop to itself.

All tunnels are already installed, and since the festival is tomorrow, Chisam now wants to buy buckets, pour water, and finish the water slide! One bucket pours water onto exactly one rooftop, and a bucket is unimaginably large, so pouring water delivers it to every rooftop reachable through the tunnels. But buckets are so expensive that Chisam wants to buy as few as possible.

Help Chisam find the minimum number of buckets needed to send water to every building rooftop!

Input

Two integers N (2 ≤ N ≤ 100,000) and M (1 ≤ M ≤ 100,000) are given. N is the number of buildings and M is the number of tunnels. Rooftop numbers are integers between 1 and N.

The next M lines each contain two integers x, y (1 ≤ x, y ≤ N), meaning a tunnel is installed from rooftop x to rooftop y.

Output

Print the minimum number of buckets needed to send water to every building rooftop.

Examples2

Example 1
Input
```
4 3
1 2
2 1
3 1
```
Expected output
```
2
```
Example 2
Input
```
10 4
6 1
9 7
9 7
4 3
```
Expected output
```
7
```