You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem B. 旅行规划2 (planb.c/cpp)

Time limit: 1 second Memory limit: 256 megabytes

问题描述

小洞这么冰雪聪明的人，当然不会被你的错误计划整蛊啦。 由于多年共事，小洞给了你一个改过自新的机会。 小洞想在一个$n$个点,$m$ 条边的无向图上进行多次旅游，每次可以选择一个点$x$作为起点，再走到 一个与$x$ 相邻的点$y$, 再走到一个与$y$ 相邻的点z 结束旅游。 作为一个经验丰富的旅行家，无论是否是同一次旅行，小洞都不希望重复的经过同一条边，他希望你给出一个旅行计划，并且小洞能进行最多次数的旅行，并给出一个次数最多的方案。

Input

第一行两个整数$n,m$，表示图的点数和边数。 接下来$m$ 行，每行两个整数$u, v$，表示一条无向边。

Output

第一行一个整数k，表示最多能进行多少次旅游。 接下来$k$ 行，每行三个整数$x, y, z$ 表示一次旅行经过的三个点。 如有多组方案能达到最多的旅游次数，任意输出一组即可。

Examples

输入样例1:

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

输出样例1:

1
2

Notes

对20% 的数据，$n ≤ 10,m ≤ 20$ 对另10% 的数据，$m = n − 1$，且图连通。 对另20% 的数据，每个点度数不超过$2$ 对100% 的数据，$n ≤ 100000,m ≤ 200000$，数据保证无重边无自环。