CF505D.Mr. Kitayuta's Technology

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Shuseki Kingdom is the world's leading nation for innovation and technology. There are nn cities in the kingdom, numbered from 11 to nn .

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 xx to city yy cannot be used to travel from city yy to city xx . The transportation within each city is extremely developed, therefore if a pipe from city xx to city yy and a pipe from city yy to city zz are both constructed, people will be able to travel from city xx to city zz instantly.

Mr. Kitayuta is also involved in national politics. He considers that the transportation between the mm pairs of city (ai,bi)(a_{i},b_{i}) ( 1<=i<=m1<=i<=m ) is important. He is planning to construct teleportation pipes so that for each important pair (ai,bi)(a_{i},b_{i}) , it will be possible to travel from city aia_{i} to city bib_{i} by using one or more teleportation pipes (but not necessarily from city bib_{i} to city aia_{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.

输入格式

The first line contains two space-separated integers nn and mm ( 2<=n<=105,1<=m<=1052<=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 mm lines describe the important pairs. The ii -th of them ( 1<=i<=m1<=i<=m ) contains two space-separated integers aia_{i} and bib_{i} ( 1<=ai,bi<=n,aibi1<=a_{i},b_{i}<=n,a_{i}≠b_{i} ), denoting that it must be possible to travel from city aia_{i} to city bib_{i} by using one or more teleportation pipes (but not necessarily from city bib_{i} to city aia_{i} ). It is guaranteed that all pairs (ai,bi)(a_{i},b_{i}) are distinct.

输出格式

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

输入输出样例

  • 输入#1

    4 5
    1 2
    1 3
    1 4
    2 3
    2 4
    

    输出#1

    3
    
  • 输入#2

    4 6
    1 2
    1 4
    2 3
    2 4
    3 2
    3 4
    

    输出#2

    4
    

说明/提示

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:

首页