H. Объединение вершин в графе
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный граф, изначально содержащий $$$n$$$ вершин и $$$m$$$ ребер. Вы можете проводить следующую операцию с этим графом:

  • выбрать две любые различные вершины графа, удалить их, а вместо них вставить новую вершину, которая соединена ребрами со всеми вершинами, с которыми были соединены обе выбранные вершины. То есть выбранные вершины — это $$$u$$$ и $$$v$$$, а новая вершина — $$$x$$$, то в граф добавляются ребра $$$(x, y)$$$ для всех таких вершин $$$y$$$, что до применения операции существовало и ребро $$$(u, 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$$$ операций, чтобы в графе осталась только одна вершина.