题目描述

如果你提到“均匀分割”的常规含义，这意味着将一个事物平等地划分。今天，你需要考虑一些不同的事情。一个图需要被分割成其子图，使得它们的节点数量是偶数，即是 2 的倍数。

你被给定一个无向连通图，其节点数量为偶数。该图需要被分割成子图，使得所有子图都是连通的且节点数量为偶数，直到无法进行进一步的分割为止。图 I.1 展示了一个示例。原始图有 8 个节点，被分割成具有 4、2 和 2 个节点的子图。所有的子图节点数量均为偶数。

图 I.1. 分割示例（样例输入/输出 1）

从数学上讲，图的偶数分割是满足以下条件的图节点子集 $V_1, \ldots, V_k$ 的集合：

1. $V_1 \cup \cdots \cup V_k$ 是输入图的所有节点的集合，并且如果 $i \neq j$，则 $V_i \cap V_j = \emptyset$。
2. 每个 $V_i$ 是非空的，并且具有偶数个元素。
3. 每个 $V_i$ 诱导一个连通子图。换句话说，$V_i$ 中的任何节点可以仅通过输入图中连接 $V_i$ 中两个节点的边互相到达。
4. 不再有进一步的分割。对于任何 $U_1 \cup U_2 = V_i$，用两个集合 $U_1$ 和 $U_2$ 替换 $V_i$ 所得到的分割不满足条件 1、2 或 3。

你的任务是找到给定图的一个偶数分割。

输入

输入由一个测试用例组成，格式如下：

第一行包含两个整数 $n$ 和 $m$。第一个整数 $n\ (2 \leq n \leq 10^5)$ 是偶数，表示待分割图的节点数量。第二个整数 $m\ (n - 1 \leq m \leq 10^5)$ 是图的边的数量。

图的节点从 $0$ 到 $n - 1$ 编号。接下来的 $m$ 行表示图的边。一行 $x_i\ y_i\ (0 \leq x_i < y_i < n)$ 表示有一条连接两个节点 $x_i$ 和 $y_i$ 的边。没有重复的边。输入图保证是连通的。

输出

如果存在将给定图的节点集分割成子集 $V_1, \ldots, V_k$ 的偶数分割，则在输出的第一行打印 $k$。接下来的 $k$ 行应描述子集 $V_1, \ldots, V_k$。子集的顺序无关紧要。第 $i$ 个子集应以 $V_i$ 的大小开头，后跟 $V_i$ 中元素的节点编号，节点编号之间用空格分隔。节点编号的顺序也无关紧要。

如果有多个偶数分割，任意一个都是可以接受的。

8 9
0 1
1 2
2 3
0 4
1 6
3 7
4 5
5 6
6 7

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

2 1
0 1

1
2 0 1