Merging Vertices in a Graph

Let every current vertex represent the set of original vertices that were merged into it.

The key invariant is:

Two current vertices/sets $A$ and $B$ are adjacent iff every original vertex in $A$ is adjacent to every original vertex in $B$ in the original graph.

For singletons this is obvious. If we merge $A$ and $B$ into $C=A\cup B$, then $C$ is adjacent to another current set $T$ iff both $A$ and $B$ were adjacent to $T$. By the invariant, that means all original edges between $A$ and $T$ exist, and all original edges between $B$ and $T$ exist. So all original edges between $A\cup B$ and $T$ exist. Induction done.

Now ask when a current set $S$ is universal. It must be adjacent to every other current set, so:

$$\forall u\in S,\ \forall v\notin S,\ (u,v) \text{ is an original edge}.$$

Notice the slightly sneaky part: edges inside $S$ do not matter. Once those vertices are merged, their internal missing edges are irrelevant. No need to overthink that bit.

Use the complement graph

In the complement graph, an edge means “this original edge is missing.”

The condition above becomes:

$$\text{there is no complement edge between } S \text{ and } V\setminus S.$$

That is exactly the definition of $S$ being a union of connected components of the complement graph.

So the whole graph operation reduces to this:

• current blocks are subsets of vertices;
• the process stops when some current block becomes a union of complement connected components.

Initial universal vertex

If some original vertex has degree $n-1$, it is already connected to all other vertices. The statement says no operations can be performed, so the answer is:

$$0\ 0$$

This also handles $n=1$.

From now on, assume no such vertex exists. Equivalently, the complement graph has no connected component of size $1$.

Minimum operations

To create a universal current vertex, we need to merge all vertices of some nonempty union of complement components.

If the chosen union has size $s$, it takes exactly $s-1$ merge operations to turn it into one block.

The smallest possible valid set is the smallest complement connected component. Therefore:

$$\text{minimum} = \min_i c_i - 1,$$

where $c_i$ are the sizes of complement connected components.

Maximum operations

Every merge reduces the number of current vertices by $1$, so the absolute upper bound is:

$$n-1.$$

Can we always reach it? Yes, as long as there was no universal vertex initially.

Since every complement component has size at least $2$, pick any complement component and choose two different vertices from it, call them $a$ and $b$.

Now imagine an ordering of all vertices where:

• $a$ is first;
• $b$ is last;
• all other vertices are in the middle in any order.

Merge vertices one by one into a growing prefix block according to this order.

Before the final operation, the growing block contains $a$ but not $b$. So it contains only part of that complement component. Therefore it is not a union of complement components, so it is not universal.

All other unmerged vertices are singletons, and no singleton is universal because we assumed no initial universal vertex.

Thus no universal vertex appears until the very last merge, when only one vertex remains. A one-vertex graph is universal vacuously. So:

$$\text{maximum} = n-1.$$

That is the whole answer once we know the complement component sizes.

Computing complement connected components efficiently

The complement graph can be dense, so building it is a non-starter.

Store the original graph. During BFS in the complement graph, from a vertex $v$ we need every still-unvisited vertex $u$ such that $(v,u)$ is not an original edge.

Maintain a set unvis of unvisited vertices. For each popped vertex $v, scan through unvis`:

• if u is not adjacent to v in the original graph, then it is reachable by a complement edge, so remove it from unvis and push it;
• otherwise leave it there.

Why is this fast enough? Each removed vertex disappears forever. Each skipped pair corresponds to an actual original edge. Since $m\le 2\cdot 10^5$, the total number of useful checks is fine. The set gives clean erase-while-iterating behavior.

Algorithm:

1. Read the graph and degrees.
2. If any degree is $n-1$, print 0 0.
3. Find connected components of the complement graph using the unvis BFS trick.
4. Let best be the smallest component size.
5. Print best - 1 and n - 1.