题目描述

有很多有关火星人的传说，比如他们的 DNA 非常复杂，他们有成千上万根手指等等，但这些都没有得到证实。同样没有得到证实的一个传说是火星人很会做 OI 题。

为了验证最后这个传说，地球人们给来自火星的外星旅人出了一道 OI 题：

给定一张 $n$ 个点 $m$ 条边的无向连通图 $G=(V,E)$，请找出最小的 $k$ 使得存在一个对点集的划分 $V_1,\ldots,V_t$ 使得：

• $\forall 1\leq x\leq t$，$\bigcup_{i=1}^x V_i$ 的导出子图连通；

• $\forall 1\leq x\leq t$，$\bigcup_{i=x}^t V_i$ 的导出子图连通；

• $\forall 1\leq x\leq t$，$|V_x|\leq k$。

注意，作为划分，还需要满足 $\bigcup_{i=1}^t V_i=V$，$V_i\cap V_j=\varnothing\ (\forall i\neq j)$，且所有 $V_i$ 非空。

请给出最小的 $k$ 以及对应的划分。

再见，You're 火星人。现在你需要完成这道题，证明火星人的智慧。

输入格式

第一行：两个整数 $n,m$，分别表示图 $G$ 的结点数和边数。

接下来 $m$ 行：每行两个整数 $x,y$，表示一条连接结点 $x,y$ 的无向边。

输出格式

第一行：两个整数 $k_{min},t$，分别表示最小的 $k$ 以及对应的划分大小。

接下来 $t$ 行：第 $i$ 行首先一个整数 $s_i$，表示 $V_i$ 的大小，然后 $s_i$ 个整数表示 $V_i$ 的元素。

如有多种划分方案，可以任意输出一种，注意你并不需要最小化 $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

提示

【样例解释】

如下图，$V_1,\ldots,V_5$ 分别是红色/橙色/绿色/蓝色/紫色点集，可以验证这满足题目条件。

【评分方式】

如果你的输出格式错误，将有可能不得分，也可能导致不可预知的错误。

如果你的输出格式正确，若你的 $k_{min}$ 正确，你将获得测试点 $50\%$ 的分数，若在此基础上你的构造方案正确，你将获得测试点 $100\%$ 的分数。

【数据范围】

对于全部数据：$2\leq n\leq 2\times 10^5$，$1\leq m\leq 2.3\times 10^5$，$1\leq x,y\leq n$，保证给出的 $m$ 条边中没有重边和自环，保证给出的图连通。