← 返回题目列表

Codeforces · 858/F

F. 巫师之旅

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

所有贝尔兰德居民都在等待巫师驾驶蓝色直升机在贝尔兰德城市上空进行前所未有的旅行!

众所周知,Berland 有 n 个城市,其中一些城市通过双向道路连接。每对城市仅由一条道路连接。不保证道路网络是连通的,即您可能无法从其他城市到达某个城市。

巡演将包含几集。在每一集中:

- 巫师将从直升机在某个城市 x 下机;
- 他将在x市免费表演并放映电影;
- 他将使用公路开车前往邻近城市y;
- 他将在y市免费表演并放映电影;
- 他将开车前往y市z的邻近地区;
- 他将在z城免费表演并放映电影;
- 他将登上直升机并飞离城市z。

众所周知,巫师不喜欢使用道路,因此他同意每条道路最多使用一次(无论方向如何)。换句话说,对于a和b之间的道路,他只能从a开车到b一次,或者从b开车到a一次,或者根本不使用这条路。

奇才队希望在不违反上述规则的情况下计划尽可能多的剧集。帮助向导!

请注意,向导可以多次访问同一城市,限制仅限于道路。

输入

第一行包含两个整数 n, m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — 分别是 Berland 的城市数量和道路数量。

道路描述如下,每行一条。每个描述都是一对两个整数ai,bi(1≤ai,bi≤n,ai≠bi),其中ai和bi是第i条道路连接的城市的id。保证没有两条道路连接同一对城市。每条路都是双向的。城市编号为 1 到 n。

Berland的路网有可能没有连通。

输出

在第一行打印 w — 最大可能的集数。接下来的 w 行应包含 x、y、z 格式的剧集——这三个整数按照向导访问的顺序表示城市的 ID。

示例

输入 #1

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

输出 #1

2
1 4 2
4 3 2

输入 #2

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

输出 #2

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