P6153 Queries

zbw was invited to a kindergarten to create problems for children.

Now zbw has $n$ items, numbered from $1 \sim n$. He will tell you $m$ conditions. Each condition contains two numbers $x, y$, meaning that item $x$ and item $y$ are the same. Because zbw is in a big hurry, he guarantees that **every condition he gives is useful; that is, each condition cannot be deduced from the previous conditions.** You need to answer how many **different kinds** of items there are.

The first line contains two integers $n$ and $m$. Then follow $m$ lines. Each line contains two numbers $x, y$, meaning that item $x$ and item $y$ are the same.

Output one integer: the number of different items.

For $20\%$ of the testdata, $n, m \le 10$. For $40\%$ of the testdata, $n, m \le 10^3$. For $60\%$ of the testdata, $n, m \le 10^5$. For $80\%$ of the testdata, $m \le 10^6$. For $100\%$ of the testdata, $1 \le n \le 10^{18}$, $1 \le m \le 10^7$. Translated by ChatGPT 5