#K82197. Maximum Valid Inspections

    ID: 35922 Type: Default 1000ms 256MiB

Maximum Valid Inspections

Maximum Valid Inspections

In a space research laboratory, there are N chambers and M bidirectional airlocks connecting these chambers. An inspection of the lab is valid if it covers an entire connected component of the lab. In other words, each connected group of chambers (where each chamber is reachable from any other within the same group) can be inspected in one go.

Your task is to determine the maximum number of valid inspections that can be performed, which is equivalent to finding the number of connected components in the lab.

The chambers are numbered from 1 to N and airlocks connect two chambers at a time. Even if a chamber is isolated (no airlocks), it is considered as a separate connected component.

Note: The relationship between chambers can be represented by an undirected graph. Hence, if there exists a path between any two chambers, they belong to the same component.

The mathematical formulation is as follows:

$$\text{Result} = \text{Number of connected components in the graph} $$

inputFormat

The first line contains two space-separated integers N and M, where N is the number of chambers and M is the number of airlocks.

This is followed by M lines, each containing two space-separated integers u and v, which indicates that there is an airlock connecting chamber u and chamber v (the connection is bidirectional).

Constraints: Chambers are numbered from 1 to N.

outputFormat

Output a single integer representing the maximum number of valid inspections, i.e. the number of connected components in the lab.

## sample
4 4
1 2
2 3
3 4
4 1
1