#P6153. 询问

询问

背景

zbw 被邀请至幼儿园给小朋友们出题。

题目描述

现在 zbw 有 nn 个物品,编号从 1∼n1 \sim n,他会告诉你 mm 个条件,每个条件包含两个数 x,yx,y,表示第 xx 个物品和第 yy 个物品是相同的。

因为 zbw 特别赶时间,所以他保证每次给出的条件都是有用的,也就是说,每次给出的条件无法由之前的条件推导得来。

你需要回答有多少种不同的物品。

输入格式

第一行两个整数 nn,mm。

之后 mm 行,每行两个数 x,yx,y,表示第 xx 个物品和第 yy 个物品是相同的。

输出格式

一个整数,不同物品的数量。

11 8 
1 2
4 3
5 4
1 3
5 6
7 10
5 10
8 9
3

提示

对于 20%20\% 的数据,n,m≤10n,m \le 10。

对于 40%40\% 的数据,n,m≤103n,m \le 10^3。

对于 60%60\% 的数据,n,m≤105n,m \le 10^5。

对于 80%80\% 的数据,m≤106m \le 10^6。

对于 100%100\% 的数据,1≤n≤10181 \le n \le 10^{18},1≤m≤1071 \le m \le 10^7。