AT_abc177_d [ABC177D] Friends

题目描述

有 $N$ 个人，从人 $1$ 到人 $N$。

给出 $M$ 条信息，每条信息表示“人 $A_i$ 和人 $B_i$ 是朋友”。同样的信息可能会被给出多次。

如果 $X$ 和 $Y$ 是朋友，且 $Y$ 和 $Z$ 是朋友，则 $X$ 和 $Z$ 也是朋友。此外，不能从这 $M$ 条信息推出的朋友关系不存在。

“恶之高桥君”想把这 $N$ 个人分成若干组，使得对于每个人来说，“同一组内没有朋友”。

请问最少需要分成多少组？

输入格式

输入从标准输入按以下格式给出。

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 3
1 2
3 4
5 1

输出 #1

3

输入输出样例 #2

输入 #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

输入 #3

10 4
3 1
4 1
5 9
2 6

输出 #3

3

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$

样例解释 1

例如，将人分为 $\{1,3\}$、$\{2,4\}$、$\{5\}$ 这 $3$ 个组，可以满足要求。

由 ChatGPT 4.1 翻译