P15071 [UOI 2024 II Stage] Matches

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$) 不会重复出现。

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

第一个示例已在题目描述中解释。 在第二个示例中，例如可以划分成以下三段：$[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 完成