← 返回题目列表

Codeforces · 190/E

E. 反击

中文机器翻译题面 查看原题

贝尔兰德成功击退了平地人的进攻,现在开始反击。

Flatland 有 n 个城市,编号从 1 到 n,其中一些城市通过双向道路连接。当且仅当这两座城市之间实际上没有道路时,弗拉特兰地图才会显示城市之间的道路(我们不知道这是一个聪明的防间谍策略还是只是节省墨水)。换句话说,如果在平原地图上两个城市通过一条道路连接起来,那么它们之间实际上没有道路。相反的情况也是如此:如果在平地地图上两个城市没有道路连接,那么实际上它们之间就有一条道路。

伯兰德人拿到了一张平原地图。现在瓦夏下士受托斯托夫将军的委托,去寻找所有这样的平原城市群,在每一组城市中,你可以沿着实际的道路从任何一个城市到达任何另一个城市。而且不同组的城市之间是无法到达的,沿着实际的道路移动。确实,将这样的群体一一消灭,比一下子包围整个平地要容易得多!

帮助下士完成这个任务,最终成为中士!不要忘记,当且仅当城市之间实际上没有道路时,平地地图才会显示城市之间的道路。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 106) — 相应地,平地地图上标记的城市数量和道路数量。

接下来的 m 行包含地图上城市的描述。第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n, ai ≠ bi)——平地地图上第 i 条道路连接的城市数量。

保证每对城市在输入中出现不超过一次。

输出

在第一行打印数字 k — 平地城市组的数量,这样在每组中,您可以通过平地道路从任何城市到达任何其他城市。同时,不同组别的城市应采用平地道路无法到达。

在接下来的 k 行中,首先打印 ti (1 ≤ ti ≤ n) — 第 i 组中的顶点数。然后打印第 i 组中以空格分隔的城市数量。

打印组的顺序和打印组中编号的顺序无关紧要。所有 k 组的总和 ti 必须等于 n。

示例

输入 #1

4 4
1 2
1 3
4 2
4 3

输出 #1

2
2 1 4
2 2 3

输入 #2

3 1
1 2

输出 #2

1
3 1 2 3

注意

在第一个样本中,仅在城市对 1-4 和 2-3 之间有道路。

在第二个样本中,城市 1 和 2 之间没有道路,但您仍然可以通过城市 3 从一个城市到达另一个城市。