H. 图中合并顶点

时间限制： 每测试 $3$ 秒
内存限制： 每测试 $512$ 兆字节

给定一个无向图，初始包含 $n$ 个顶点和 $m$ 条边。你可以在此图上执行以下操作：

• 选择图中任意两个不同的顶点，移除它们，并插入一个新顶点，该新顶点与所有同时与两个被选顶点都相连的顶点相连。即，若选择的顶点为 $u$ 和 $v$，新顶点为 $x$，则对于所有同时存在边 $(u, y)$ 和 $(v, y)$ 的顶点 $y$，向图中添加边 $(x, y)$。

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

你的任务是计算最少和最多可以执行的操作次数。

---

输入格式

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

接下来 $m$ 行中的第 $i$ 行包含两个整数 $x_i, y_i$ $(1 \leq x_i, y_i \leq n;\ x_i \neq 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$ 次操作。

最长操作序列如下：

• 选择顶点 $1$ 和 $5$。设新顶点为 $6$；它将不与任何剩余顶点相连。
• 选择顶点 $2$ 和 $4$。设新顶点为 $7$；它将与顶点 $3$ 相连。
• 选择顶点 $7$ 和 $3$。设新顶点为 $8$；它将不与任何剩余顶点相连。
• 选择顶点 $6$ 和 $8$。图中只剩一个顶点，因此它与所有其他顶点相连。共 $4$ 次操作。

第二个样例：图中已经存在一个顶点（顶点 $1$）与所有其他顶点相连，因此不能执行任何操作。答案为 $0, 0$。

第三个样例：无论采用何种方式，都需要 $199999$ 次操作才能将图缩减到只剩一个顶点。答案为 $199999, 199999$。