← 返回题目列表

AtCoder · abc177_d

D. 朋友

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 称为 Person 的人 1 通过人 N.

你被给予 M 事实“人 A_i 和人 B_i 是朋友。”同一个事实可能会被多次给出。

If X 和 Y 是朋友,并且 Y 和 Z 是朋友,那么 X 和 Z 也是朋友。没有什么友谊是不能从友情中衍生出来的 M 给出事实。

高桥邪恶想要瓜分 N 将人分成一定数量的组,以便每个人在他/她的组中没有朋友。

他至少需要组多少组?

约束

  • 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

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
\vdots
A_M B_M

输出

打印答案。


示例输入 1

5 3
1 2
3 4
5 1

示例输出 1

3

将它们分为三组,例如 \{1,3\}, \{2,4\},和 \{5\} 实现了目标。


示例输入 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