A directed graph G = (V, A)
consists of a set of vertices V and a set of arcs A.
An arc is an ordered pair (u, v), where u, v ∈ V.
A path from a vertex v_{i1} to a vertex v_{ik}
is a sequence of arcs
(v_{i1}, v_{12}), (v_{i2}, v_{i3}), …, (v_{ik−1}, v_{ik}).
By definition, there is always a path from every vertex to itself.

Consider the following equivalence relation: two vertices u and v of G are related if, and only if, there is a path from u to v and a path from v to u. Every equivalence class resulting from this definition is called a strongly connected component of G.

Given a directed graph, calculate how many strongly connected components it has.

Input

Input begins with the number of cases.
Each case consists of the number of vertices n and the number of arcs m,
followed by m pairs (u, v).
Vertices are numbered starting at 0.
There are not repeated arcs, nor self-arcs (v, v).
Assume 1 ≤ n ≤ 10^{4}.

Output

For every graph, print its number of strongly connected components.

Public test cases

**Input**

3 3 3 0 1 1 2 2 0 7 7 0 1 1 2 2 0 3 4 4 6 6 3 0 6 6 7 0 1 0 2 1 3 2 3 3 4 4 2 5 4

**Output**

Graph #1 has 1 strongly connected component(s). Graph #2 has 3 strongly connected component(s). Graph #3 has 4 strongly connected component(s).

Information

- Author
- Xavier Martínez
- Language
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python
- Event
- Quart Concurs de Programació de la UPC - Semifinal
- Date
- 2006-09-20