PA2014Final Krolestwo

时间限制:20s      空间限制:128MB

题目描述

你有一个无向连通图,边的总数为偶数。
设图中有k个奇点(度数为奇数的点),你需要把它们配成k/2个点对(显然k被2整除)。对于每个点对(u,v),你需要用一条长度为偶数(假设每条边长度为1)的路径将u和v连接。每条路径允许经过重复的点,但不允许经过重复的边。这k/2条路径之间也不能有重复的边。


输入格式

第一行有两个整数n,m(2<=n,m<=250000),分别表示点数、边数,m为偶数。
接下来m行,每行两个整数a,b(1<=a,b<=n,a≠b),表示a,b间连有一条边。不存在重边。保证奇点的数目不为零。


输出格式

如果你认为无解就输出NIE。
设图中有k个奇点,则输出由k/2部分组成,每个部分包含两行:第一行为u,v,l,表示连接的两个点,及路径长度。第二行为空格隔开的l个整数,表示u到v的路径。边按照输入顺序从1到m编号。
若有多组答案,任意输出其中一个。


样例输入

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

样例输出

样例输出:
1 5 2
6 5
2 4 2
8 4
另一种合法输出:
1 5 6
1 2 3 7 6 5
2 4 2
8 4

提示

没有写明提示


题目来源

鸣谢Jcvb