Condensation of the graph
Very easy
Execution time limit is 2 seconds
Runtime memory usage limit is 128 megabytes
Find the number of edges in the condensation of a given directed graph.
The condensation of a directed graph is a directed graph , whose vertices are strongly connected components of , and the edge in is present only if there exists at least one edge between the vertices of corresponding connected components.
The graph condensation does not contain multiple edges.
Input
The first line contains number of vertices and number of edges in the graph. Each of the next lines describe the edge of the graph. The -th edge is given with the starting and the ending vertex of the graph. The input graph can contain the multiple edges and loops.
Output
Print the number of edges in graph condensation.
Examples
Input #1
Answer #1
Submissions 5K
Acceptance rate 25%