CF2141H.Merging Vertices in a Graph

给定一个无向图，最初包含 $n$ 个顶点和 $m$ 条边。你可以对该图进行如下操作：

• 任意选择两个不同的顶点，将它们删除，并插入一个新顶点，使其与所有同时与所选两个顶点相连的顶点建立边。即，如果选择了顶点 $u$ 和 $v$，新顶点为 $x$，则对于所有满足 $(u, y)$ 和 $(v, y)$ 边均存在的顶点 $y$，添加新的边 $(x, y)$。

该操作可以进行任意多次，直到图中存在一个顶点与所有其他顶点直接有边相连。一旦出现这样的顶点，过程立即结束。此外，如果最初图中就存在这样的顶点，则不能进行任何操作。

你的任务是统计最少和最多可以进行多少次操作。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le \min(\frac{n(n - 1)}{2}, 2 \cdot 10^5)$）。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$（$1 \le x_i, y_i \le n$，$x_i \ne y_i$），表示第 $i$ 条边的两个端点。任意一对顶点之间至多只有一条边。

输出两个整数，分别表示最少和最多可以进行的操作次数。

在第一个样例中，最短的操作序列如下：

• 选择顶点 $1$ 和 $3$，新顶点会与 $2$、$4$、$5$ 相连，且图中没有其他顶点。

最长的操作序列如下：

• 选择顶点 $1$ 和 $5$。记新顶点为 $6$，它不会与剩下的任何顶点相连。
• 选择顶点 $2$ 和 $4$。记新顶点为 $7$，它会与顶点 $3$ 相连。
• 选择顶点 $7$ 和 $3$。记新顶点为 $8$，它不会与剩下的任何顶点相连。
• 选择顶点 $6$ 和 $8$。现在图中只剩下一个顶点，因此它与所有其他顶点相连。

在第二个样例中，图中已经存在与所有其它顶点相连的顶点，因此无法进行任何操作。

在第三个样例中，无论采用何种方式，都需要 $199999$ 次操作才能只剩下一个顶点。

由 ChatGPT 5 翻译