Problem B
Staying Connected

An undirected, unweighted graph $G$ is specified by a set of vertices $V$ and a set of edges $E$, where each edge connects two vertices (and, thus, is specified by a pair of vertices). For example, take this graph:

This graph is defined as $V=\{ 0,1,2,3,4\} $ and $E=\{ (0,1),(0,3),(0,4),(1,4),(2,3),(3,4)\} $. Note that there is a single pair of vertices per edge (i.e., since this is an undirected graph, we do not need to include both $(0,1)$ and $(1,0)$ in $E$; just one is enough to specify that there exists an edge between vertex 0 and vertex 1).

In the above graph, all the vertices are connected. i.e., for all possible pairs of vertices $(v_1, v_2)$ in the graph, it is possible to find a path from $v_1$ to $v_2$ (e.g., vertex $0$ and vertex $2$ are not directly connected with an edge, but you can reach vertex $2$ from vertex $0$ by going through vertex $3$). Here is an example of a graph where all the vertices are not connected:

This graph is defined as $V=\{ 0,1,2,3,4\} $ and $E=\{ (0,1), (0,2), (1,2), (3,4)\} $. Note that this does not specify two graphs, but rather a single graph with two connected components. A connected component is a subgraph $G’$ of a graph $G$ such that, for every possible pair of vertices in $G’$, there exists a path between those vertices and there are no paths in $G$ that connect the vertices in $G’$ to any of the other vertices in $G$. So, the two connected components in the above graph are $V_1=\{ 0,1,2\} $ and $V_2=\{ 3,4\} $.

As a counterexample, vertices $\{ 0,1\} $ would not be a connected component because, although there does exists a path between all possible pairs of vertices (in this case, just $0$ and $1$), the graph also contains paths connecting $0$ and $1$ to other vertices in the graph.

You will write a program that, given the specification of a graph $G$, will count the number of connected components in that graph. An easy way of doing this is by using depth-first search:

function dfs(graph, root_vertex)
    Mark root_vertex as "visited"
    for each vertex v connected to root_vertex by an edge do
        if v is not marked as "visited"
            Mark v as "visited"
            dfs(graph, v)
        end if
    end for
end function

Take into account that depth-first search does not solve the problem entirely. However, doing a depth-first search starting at a vertex in a connected component will result in all the vertices in that connected component being marked as “visited”. This is a useful stepping stone towards figuring out the number of connected components.

Input

The input contains the specification of a single graph $G$. The first two lines contain the number of vertices $|V|$ ($1 \leqslant |V| \leqslant 200$) and the number of edges $|E|$ ($0 \leqslant |E| \leqslant \frac{|V|\cdot (|V|-1)}{2}$). The input is followed by $|E|$ lines, each containing a pair of integers separated by a single space. This pair of integers specifies the vertices connected by that edge. We assume that vertices are numbered from 0 (so, if $|V|=4$ then $V=\{ 0,1,2,3\} $).

Note that the two sample inputs correspond to the two example graphs shown above.

Output

You must print a single integer: the number of connected components in $G$.

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

1

5
4
0 1
0 2
1 2
3 4

2