Mr. Kitayuta's Technology

1000ms

262144K

Description:

Shuseki 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⁵, 1 ≤ m ≤ 10⁵), 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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Note:

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

$\text{[math]}$

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

$\text{[math]}$

Informação

Provedor Codeforces

Código CF505D