logo AlgoBeat OnlineJudge
登录 注册

#213839. 朝花

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定一张 个点 条边简单无向图, 定义一次操作为:

  • 选出 个互不相同的节点;

  • 把这些节点两两之间的边的状态取反(有边改为无边,无边改为有边);

  • 该操作的代价为

让你在 的代价内将此图消成空图。

可以证明在给定数据范围一定有解。

输入格式

第一行两个数

第 2 至 行每行两个数 表示图中的一条边。

输出格式

第一行一个数 表示你的操作总次数。

第 2 行至第 行,第 行先输出一个数 ,后面 个数表示第 次操作你选择的节点。

样例

样例输入 1

6 4
1 2
3 4
1 3
2 4

样例输出 1

2
3 1 2 3
3 2 3 4

样例输入 2

6 1
1 2

样例输出 2

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

数据范围与提示

样例解释

样例 1 中初始的边集为 ,第一次操作后变为 ,第二次操作后变为空集。

数据范围

对于 的数据,保证每个点的度数为偶数。

对于所有数据,