You are given an undirected graph, initially containing $$$n$$$ vertices and $$$m$$$ edges. You can perform the following operation on this graph:

Choose any two distinct vertices of the graph, remove them, and insert a new vertex that is connected by edges to all vertices that were connected to both of the chosen vertices. That is, if the chosen vertices are $$$u$$$ and $$$v$$$, and the new vertex is $$$x$$$, then edges $$$(x, y)$$$ are added to the graph for all such vertices $$$y$$$ that both edges $$$(u, y)$$$ and $$$(v, y)$$$ existed before the operation.

This operation can be performed any number of times until there exists a vertex in the graph that is directly connected by edges to all other vertices. As soon as such a vertex appears, the process ends. Additionally, if such a vertex already exists in the graph initially, no operations can be performed.

Your task is to count the minimum and maximum number of operations that you can perform.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le m \le \min(\frac{n(n - 1)}{2}, 2 \cdot 10^5)$$$).

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge. There is at most one edge between each pair of vertices.

Output

Output two integers — the minimum and the maximum number of operations.

Note

In the first example, the shortest sequence of operations is as follows:

Choose vertices $$$1$$$ and $$$3$$$, then the resulting vertex will be connected to vertices $$$2$$$, $$$4$$$, $$$5$$$, and there are no other vertices in the graph.

The longest sequence of operations is as follows:

Choose vertices $$$1$$$ and $$$5$$$. Let the resulting vertex be $$$6$$$; it will not be connected to any of the remaining vertices.
Choose vertices $$$2$$$ and $$$4$$$. Let the resulting vertex be $$$7$$$; it will be connected to vertex $$$3$$$.
Choose vertices $$$7$$$ and $$$3$$$. Let the resulting vertex be $$$8$$$; it will not be connected to any of the remaining vertices.
Choose vertices $$$6$$$ and $$$8$$$. Only one vertex will remain in the graph, so it will be connected to all other vertices.

In the second example, there is already a vertex in the graph that is connected to all others, so no operations can be performed.

In the third example, it will take $$$199999$$$ operations to leave only one vertex in the graph, regardless of the approach.

#	Name	Rating↕	Solved↕
2141H	Merging Vertices in a Graph *special dfs and similar dsu graphs	2700	85
1940A	Parallel Universes *special constructive algorithms dfs and similar dsu graphs	unrated	106
1940C	Burenka and Pether *special data structures dfs and similar divide and conquer dsu graphs sortings trees	unrated	44

Problemset