Codeforces Round 286 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Mr. Kitayuta's Technology

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputShuseki Kingdom is the world's leading nation for innovation and technology. There are *n* cities in the kingdom, numbered from 1 to *n*.

Thanks to Mr. Kitayuta's research, it has finally become possible to construct teleportation pipes between two cities. A teleportation pipe will connect two cities unidirectionally, that is, a teleportation pipe from city *x* to city *y* cannot be used to travel from city *y* to city *x*. The transportation within each city is extremely developed, therefore if a pipe from city *x* to city *y* and a pipe from city *y* to city *z* are both constructed, people will be able to travel from city *x* to city *z* instantly.

Mr. Kitayuta is also involved in national politics. He considers that the transportation between the *m* pairs of city (*a*_{i}, *b*_{i}) (1 ≤ *i* ≤ *m*) is important. He is planning to construct teleportation pipes so that for each important pair (*a*_{i}, *b*_{i}), it will be possible to travel from city *a*_{i} to city *b*_{i} by using one or more teleportation pipes (but not necessarily from city *b*_{i} to city *a*_{i}). Find the minimum number of teleportation pipes that need to be constructed. So far, no teleportation pipe has been constructed, and there is no other effective transportation between cities.

Input

The first line contains two space-separated integers *n* and *m* (2 ≤ *n* ≤ 10^{5}, 1 ≤ *m* ≤ 10^{5}), denoting the number of the cities in Shuseki Kingdom and the number of the important pairs, respectively.

The following *m* lines describe the important pairs. The *i*-th of them (1 ≤ *i* ≤ *m*) contains two space-separated integers *a*_{i} and *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*, *a*_{i} ≠ *b*_{i}), denoting that it must be possible to travel from city *a*_{i} to city *b*_{i} by using one or more teleportation pipes (but not necessarily from city *b*_{i} to city *a*_{i}). It is guaranteed that all pairs (*a*_{i}, *b*_{i}) are distinct.

Output

Print the minimum required number of teleportation pipes to fulfill Mr. Kitayuta's purpose.

Examples

Input

4 5

1 2

1 3

1 4

2 3

2 4

Output

3

Input

4 6

1 2

1 4

2 3

2 4

3 2

3 4

Output

4

Note

For the first sample, one of the optimal ways to construct pipes is shown in the image below:

For the second sample, one of the optimal ways is shown below:

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/15/2024 18:14:43 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|