CF2141H Merging Vertices in a Graph

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.

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 two integers — the minimum and the maximum number of operations.

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.