Partitioning Graph into Connected Prefix and Suffix Subgraphs

There are many legends about Martians – for example, that their DNA is extremely complex and they have thousands of fingers – but none of these have been confirmed. One unconfirmed legend states that Martians are adept at solving OI problems. To verify this legend, Earth scientists present the following problem to an extraterrestrial visitor from Mars:

Given an undirected connected graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges, find the smallest positive integer \(k\) for which there exists a partition of the vertex set into nonempty subsets \(V_1, V_2, \ldots, V_t\) satisfying the following conditions:

1. The subgraph induced by \(\bigcup_{i=1}^x V_i\) is connected for every \(1 \le x \le t\).
2. The subgraph induced by \(\bigcup_{i=x}^t V_i\) is connected for every \(1 \le x \le t\).
3. \(|V_x| \le k\) for every \(1 \le x \le t\).

Note that as a partition, it is also required that \(\bigcup_{i=1}^{t} V_i = V\) and \(V_i \cap V_j = \varnothing\) for all \(i \neq j\).

Your task is to output the minimum possible \(k\) along with one corresponding valid partition. Prove the wisdom of the Martians!

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) \((1 \le n \le 10^5,\ n-1 \le m \le 10^5)\), representing the number of vertices and the number of edges, respectively. The following \(m\) lines each contain two space-separated integers \(u\) and \(v\) \((1 \le u,v \le n, u \neq v)\), denoting an undirected edge between vertices \(u\) and \(v\). It is guaranteed that the graph is connected.

outputFormat

Output a valid answer in the following format:

1. The first line contains the minimum possible integer \(k\).
2. The second line contains a single integer \(t\) indicating the number of parts in the partition.
3. Then follow \(t\) lines. The \(i\)-th of these lines starts with an integer \(|V_i|\) (the size of the \(i\)th part), followed by \(|V_i|\) space-separated integers, representing the vertices in that part.

If multiple partitions exist meeting the conditions, you may output any one of them.

sample

3 2
1 2
2 3

3
1
3 1 2 3