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$

输出格式

输出答案。

5 3
1 2
3 4
5 1

3

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

4

10 4
3 1
4 1
5 9
2 6

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,3\}$、$\{2,4\}$ 和 $\{5\}$ 可以达到目的。

标签: AtCoder|abc177D

来源

AtCoder|abc177D