说明

Anton 发明了一项名为水球（类似彩弹，但用水）的新团队运动。他想与他的 $n$ 个朋友分享这项发明。Anton 与所有朋友关系都很好，但不能保证他的朋友们彼此之间关系同样融洽。具体来说，我们知道编号为 $a_i$ 的朋友与编号为 $b_i$ 的朋友存在冲突。

Anton 得到了一个包含 $m$ 个冲突对 ($a_i;b_i$) 的列表。现在，看似可以将玩家分成两队，但对 Anton 来说并不那么简单……

他想要将这些 $m$ 个冲突对划分成若干段，使得：

• 每个冲突对恰好属于一段；
• 仅考虑每段内的冲突关系时，可以将所有人分成两队，使得同一队中没有两个相互冲突的人。

例如，假设我们有冲突对数组 $[(1, 2), (2, 3), (1, 3)]$。我们可以将前两个对放在第一段。此时，可以组成队伍：$[1, 3]$ 和 $[2]$。在第二段中，我们可以取最后一个对。$1$ 和 $3$ 必须分在不同队伍，$2$ 可以在任意一队。或者，我们可以将第一个对分配给第一段，最后两个对分配给第二段。注意，我们不能将第一个和第三个对放在同一段，而将第二个对放在另一段，因为一段应当只包含连续的冲突对。我们也不能将所有对放在同一段，因为那样总会存在一个队伍中有相互冲突的人。

Anton 又把问题描述复杂化了，现在他自己无法解决这个问题。请帮助他，告诉他满足上述条件时，最少可以将这些对划分成多少段。

输入格式

• 第一行包含两个整数 $n$、$m$（$1 \le n, m \le 10^6$）——朋友数量和冲突关系数量。
• 接下来的 $m$ 行，每行包含两个整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$，$a_i \neq b_i$），表示朋友 $a_i$ 与朋友 $b_i$ 存在冲突。

保证任何冲突对 ($a;b$) 不会重复出现。

输出格式

输出一个整数——问题的答案。

3 3
1 2
2 3
1 3

2

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

3

提示

第一个示例已在题目描述中解释。

在第二个示例中，例如可以划分成以下三段：$[1;6]$、$[7;9]$、$[10;10]$。

• 在第一段中，可以组成队伍 $[1,4]$ 和 $[2,3,5]$ —— $1$ 和 $4$ 不冲突，且 $(2;3)$、$(2;5)$、$(3;5)$ 也不冲突。
• 在第二段中，可以组成队伍 $[1,3]$ 和 $[2,4,5]$ —— $1$ 和 $3$ 不冲突，且 $(2;4)$、$(2;5)$、$(4;5)$ 也不冲突。
• 在第三段中，可以组成队伍 $[1,2]$ 和 $[3,4,5]$ —— $1$ 和 $2$ 不冲突，且 $(3;4)$、$(3;5)$、$(4;5)$ 也不冲突。

评分细则

• （$4$ 分）：$n \le 3$；
• （$7$ 分）：$n \le 10$；
• （$15$ 分）：$n, m \le 5000$；
• （$13$ 分）：输入中的冲突对随机生成；这意味着从所有 $\frac{n (n-1)}{2}$ 个对中随机选择了 $m$ 个对；
• （$14$ 分）：每个人冲突的对象不超过 $10$ 个；
• （$19$ 分）：$n \le 10^5$；
• （$17$ 分）：$n \le 2 \cdot 10^5$；
• （$11$ 分）：无额外限制。

翻译由 DeepSeek V3 完成