给你一个无向图,最初包含 $$$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 71 23 22 43 51 45 14 3
输出复制
1 4
输入复制
4 31 21 31 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$$$ 操作才能在图中仅留下一个顶点。