Treetop Walkway

Time limit5sMemory limit512 MB

Summary

Given a weakly connected directed graph, find the minimum number of edges to add so every vertex reaches every other.

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

Problem

The amusement park keeps wide patches of forest between its attractions. A treetop walkway lets visitors move through the canopies and look out over the hills and lakes around the park.

The walkway is built from wooden platforms fixed near the treetops at different heights above the ground, joined by narrow wooden paths. Each path joins exactly two platforms, and the number of paths meeting at a platform differs from platform to platform. Ignoring the direction of travel, every platform can be reached from every other platform along the paths.

To raise the safety standard and to relieve crowding at a few spots, the management made every path strictly one way. Once the directions were fixed, a problem showed up. Walking only in the prescribed directions, some platforms can no longer be reached from some other platforms. The management chose the directions on aesthetic and operational grounds, so the directions stay as they are.

The repair is to build extra one way paths between platforms that already exist. No platform is added and no old path changes direction. After the new paths are built, every platform must be reachable from every other platform along the paths. The management wants to build as few new paths as possible.

Find that smallest number of new paths.

Input

The input holds several test cases and ends at the end of the file.

Each test case starts with a line holding two integers $N$ and $M$ ( $1 \le N \le 10^5$ , $0 \le M \le 2 \cdot 10^5$ ), the number of platforms and the number of existing paths. The platforms are labeled $1$ through $N$ .

Each of the next $M$ lines holds two different platform labels $A$ and $B$ , which means there is a one way path leading from $A$ to $B$ . Inside one test case the ordered pair $(A, B)$ never appears twice, but $A \to B$ and $B \to A$ may both appear. Ignoring the directions, the paths of a test case connect all $N$ platforms.

Output

For each test case, print one line holding a single integer $R$ , the smallest number of new one way paths that makes every platform reachable from every other platform. Print only this number. You do not have to print the new paths themselves.

Examples3

Example 1

Input

Expected output

1
3
3

Example 2
Input
```
1 0
```
Expected output
```
0
```
Example 3
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
0
```