<PREV Problem:
NEXT>
Solved by 212 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Stations

Time limit = 5 second(s)

You are given directed graph. Put minimal number of stations in vertises so that for any vertex A there will be vertex B with station so that there is route from B to A.

Input. Vertises are denoted by integers 1, 2, ..., V.

Input are given in the form

V E
f1 t1
f2 t2
...

fE tE

Here V and E is number of vertises and number of edges in the graph. V < 2000, E < 1001001. Than E lines with vertises description follow. Each line contains identifiers of edge ends (FROM and TO).

Output. One line with number S — minimal number of stations.

Input#1
3 3
1 2
2 3
3 1
Output#1
1

Input#2
6 7
1 2
2 3
3 6
6 1
3 4
5 4
1 3
Output#2
2


Author:
Well-known problem. Tests and description by Artem Voroztsov.
4 May 2006

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 23.20.166.68