Problem Description

There are many legends about Martians, such as their DNA being very complex, or that they have tens of thousands of fingers, and so on, but none of these have been confirmed. Another unconfirmed legend is that Martians are very good at solving OI problems.

To verify this last legend, people on Earth gave an OI problem to an alien traveler from Mars:

Given a connected undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges, find the minimum $k$ such that there exists a partition of the vertex set $V_1,\ldots,V_t$ satisfying:

• $\forall 1\leq x\leq t$, the induced subgraph of $\bigcup_{i=1}^x V_i$ is connected;

• $\forall 1\leq x\leq t$, the induced subgraph of $\bigcup_{i=x}^t V_i$ is connected;

• $\forall 1\leq x\leq t$, $|V_x|\leq k$.

Note that, as a partition, it must also satisfy $\bigcup_{i=1}^t V_i=V$, $V_i\cap V_j=\varnothing\ (\forall i\neq j)$, and all $V_i$ are non-empty.

Output the minimum $k$ and a corresponding partition.

Goodbye, You're Martian. Now you need to finish this problem and prove the wisdom of Martians.

Input Format

The first line: two integers $n,m$, representing the number of vertices and edges of graph $G$.

The next $m$ lines: each line contains two integers $x,y$, representing an undirected edge connecting vertices $x,y$.

Output Format

The first line: two integers $k_{min},t$, representing the minimum $k$ and the size of the corresponding partition.

The next $t$ lines: on the $i$-th line, first an integer $s_i$, representing the size of $V_i$, followed by $s_i$ integers representing the elements of $V_i$.

If there are multiple valid partitions, you may output any one of them. Note that you do not need to minimize $t$.

7 7
1 2
1 3
1 5
1 6
4 5
5 6
6 7

2 5
1 2
2 1 3
2 5 4
1 6
1 7

Hint

[Sample Explanation]

In the figure below, $V_1,\ldots,V_5$ are the red / orange / green / blue / purple vertex sets, respectively. You can verify that they satisfy the conditions.

[Scoring]

If your output format is incorrect, you may get no points, and it may also cause unpredictable errors.

If your output format is correct, then if your $k_{min}$ is correct, you will get $50\%$ of the score for the test point. If, on this basis, your construction is also correct, you will get $100\%$ of the score for the test point.

[Constraints]

For all data: $2\leq n\leq 2\times 10^5$, $1\leq m\leq 2.3\times 10^5$, $1\leq x,y\leq n$. It is guaranteed that among the given $m$ edges there are no multiple edges and no self-loops, and the given graph is connected.

Translated by ChatGPT 5