Minimal Shortest Path Cover

You are given an undirected graph with n vertices and m edges. A path is a sequence of vertices such that each consecutive pair is connected by an edge. In each connected component of the graph, you can cover all vertices by selecting a single shortest path that spans that component.

Your task is to determine the minimum number of shortest paths required to cover all vertices. In other words, compute the number of connected components in the graph.

More formally, let the graph be represented as \(G = (V, E)\) with \(|V| = n\) and \(|E| = m\). A connected component is a maximal set of vertices \(C \subseteq V\) such that for any two vertices \(u, v \in C\), there exists a path between \(u\) and \(v\). The answer is the number of these connected components, which is also the minimal number of shortest paths needed to cover all vertices.

Input constraints:

• \(1 \leq n \leq 10^5\)
• \(0 \leq m \leq 10^5\)
• Edges are given in a 1-indexed format.

inputFormat

The first line contains two integers n and m, separated by a space, representing the number of vertices and edges respectively.

The following m lines each contain two integers u and v, indicating an undirected edge between vertices u and v.

All input is read from standard input (stdin).

outputFormat

Output a single integer representing the minimal number of shortest paths required to cover all vertices (i.e., the number of connected components in the graph).

The result should be written to standard output (stdout).

## sample

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

1