Description

There are several computers, and some pairs are connected by bidirectional data lines. If a computer receives the data, then every computer that is reachable from it via the data lines will also receive the data. Now you have the data. What is the minimum number of computers into which you must input the data so that all computers receive it?

Input Format

The first line contains two integers $n, m$. Here $n$ is the number of vertices, and $m$ is the number of edges. The next $m$ lines each contain two integers $p, q$, indicating that there is a bidirectional data line between $p$ and $q$.

Output Format

Output one integer, the minimum number of computers into which you must input the data.

4 5
1 2
1 3
2 3
2 1
3 4

1

Hint

• For $30\%$ of the testdata, $n \le 100$, $m \le 1000$.
• For $60\%$ of the testdata, $n \le 2000$.
• For $100\%$ of the testdata, $0 \le n \le 10^5$, $0 \le m \le 2 \times 10^5$, $1 \le p, q \le n$.

The graph may contain multiple edges and self-loops.

Translated by ChatGPT 5