TheGraf
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. For the given graph determine minimal number of edges needed to add in the graph such that it becomes strongly connected.
Input The first line of input contains two integers n (2 ≤ n ≤ 20.000) and m (1 ≤ m ≤ 50.000), the number of vertices and edges in graph, respectively. Each of the following m lines contains two integers u and v (both between 1 and n, inclusive), representing directed edge from vertex u to vertex v.
Output In the first and only line of output print minimal number of edges needed to add in the graph such that it becomes strongly connected.
Input:
3 2
1 2
2 3
Output:
1Submit solution
Sign in to submit a solution.