A6271. 朋友分组
编程题
普及/提高-
知识点
题目描述
有 $N$ 个人，从人 $1$ 到人 $N$。
给出 $M$ 条信息，每条信息表示「人 $A_i$ 和人 $B_i$ 是朋友」。同样的一对信息可能会被给出多次。
如果 $X$ 和 $Y$ 是朋友，且 $Y$ 和 $Z$ 是朋友，则 $X$ 和 $Z$ 也是朋友。除此之外，不能从这 $M$ 条信息推出的朋友关系一律视为不存在。
现在，「恶之 Welcome24ever」想把这 $N$ 个人分成若干组，使得**对于每个人来说，同一组内没有他的朋友**。
请你求出，最少需要分成多少组。
给出 $M$ 条信息，每条信息表示「人 $A_i$ 和人 $B_i$ 是朋友」。同样的一对信息可能会被给出多次。
如果 $X$ 和 $Y$ 是朋友，且 $Y$ 和 $Z$ 是朋友，则 $X$ 和 $Z$ 也是朋友。除此之外，不能从这 $M$ 条信息推出的朋友关系一律视为不存在。
现在，「恶之 Welcome24ever」想把这 $N$ 个人分成若干组，使得**对于每个人来说，同一组内没有他的朋友**。
请你求出，最少需要分成多少组。
输入格式
从标准输入读入。
第一行包含两个整数 $N$ 和 $M$。
接下来 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示人 $A_i$ 和人 $B_i$ 是朋友（可能会重复出现同一对人）。
> $N\ M$
> $A_1\ B_1$
> $\vdots$
> $A_M\ B_M$
第一行包含两个整数 $N$ 和 $M$。
接下来 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$，表示人 $A_i$ 和人 $B_i$ 是朋友（可能会重复出现同一对人）。
> $N\ M$
> $A_1\ B_1$
> $\vdots$
> $A_M\ B_M$
输出格式
输出一个整数，表示最少需要分成的组数。
输入输出样例
输入 #1
5 3 1 2 3 4 5 1
输出 #1
3
输入 #2
4 10 1 2 2 1 1 2 2 1 1 2 1 3 1 4 2 3 2 4 3 4
输出 #2
4
输入 #3
10 4 3 1 4 1 5 9 2 6
输出 #3
3
说明/提示
### 限制条件
- $2 \le N \le 2 \times 10^5$
- $0 \le M \le 2 \times 10^5$
- $1 \le A_i, B_i \le N$
- $A_i \ne B_i$
### 样例解释 1
例如，可以将人分为 $\{1,3\}$、$\{2,4\}$、$\{5\}$ 共 $3$ 个组，满足同一组内互相都不是朋友。
- $2 \le N \le 2 \times 10^5$
- $0 \le M \le 2 \times 10^5$
- $1 \le A_i, B_i \le N$
- $A_i \ne B_i$
### 样例解释 1
例如，可以将人分为 $\{1,3\}$、$\{2,4\}$、$\{5\}$ 共 $3$ 个组，满足同一组内互相都不是朋友。