favorite We need a little bit of your help to keep things running, click on this banner to learn more

Strong Connected Components

Strong connectivity

We call a strongly connected component in a directed graph an arbitrary set of vertices such that every vertex in this set there is a path to any other vertex of the set, and there is another set with the same property that contains this set.

Given a directed graph. Find the number of different components of strong connectivity in it.


The first line contains two integers n and m (1n10, 0m90) - number of vertices and edges in the graph, respectively. The next m lines describe the edges: i-th of these lines contains two integers ui and vi (1ui, vin) - the start and the end of the i-th edge respectively. It is guaranteed that the graph has no loops or multiple edges.


The first line of the output file output a single number - the number of strongly connected components of the graph.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 2
1 2
2 3
Output example #1
Input example #2
5 4
3 1
1 2
2 3
4 5
Output example #2
Source SСS - 2011 Sevastopol 08/08/2011 d.2 1st League