← 返回题目列表

Codeforces · 2141/H

H. 合并图中的顶点

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

给你一个无向图,最初包含 $$$n$$$ 个顶点和 $$$m$$$ 个边。您可以对该图执行以下操作:

  • 选择图形的任意两个不同的顶点,将其删除,然后插入一个通过边连接到所有已连接顶点的新顶点 所选顶点的 两者 。也就是说,如果所选顶点是 $$$u$$$ 和 $$$v$$$,并且新顶点是 $$$x$$$,则将边 $$$(x, y)$$$ 添加到所有此类顶点 $$$y$$$ 的图中,使得边 $$$(u, y)$$$ 和 $$$(v, y)$$$ 和 $$$(v, 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$$$ 条边的端点。每对顶点之间至多有一条边。

输出

输出两个整数——最小和最大操作数。

示例

输入
复制

5 7
1 2
3 2
2 4
3 5
1 4
5 1
4 3

输出
复制

1 4

输入
复制

4 3
1 2
1 3
1 4

输出
复制

0 0

输入
复制

200000 0

输出
复制

199999 199999

注意

在第一个示例中,最短的操作序列如下:

  • 选择顶点 $$$1$$$ 和 $$$3$$$,则生成的顶点将连接到顶点 $$$2$$$、$$$4$$$、$$$5$$$,并且图中没有其他顶点。

最长的操作序列如下:

  • 选择顶点 $$$1$$$ 和 $$$5$$$。令结果顶点为$$$6$$$;它不会连接到任何剩余的顶点。
  • 选择顶点 $$$2$$$ 和 $$$4$$$。令结果顶点为$$$7$$$;它将连接到顶点$$$3$$$。
  • 选择顶点 $$$7$$$ 和 $$$3$$$。令结果顶点为$$$8$$$;它不会连接到任何剩余的顶点。
  • 选择顶点 $$$6$$$ 和 $$$8$$$。图中将仅保留一个顶点,因此它将连接到所有其他顶点。

在第二个示例中,图中已经有一个顶点与所有其他顶点相连,因此无法执行任何操作。

在第三个示例中,无论采用哪种方法,都需要 $$$199999$$$ 操作才能在图中仅留下一个顶点。