← 返回题目列表

Codeforces · 405/E

E. 图形切割

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

小克里斯正在参加切图比赛。他是一名职业选手。考验他能力的时刻到了。

Chris 得到一个简单的无向连通图,有 n 个顶点(编号从 1 到 n)和 m 个边。问题是将其切割成长度为 2 的边不同路径。形式上,Chris 必须将图的所有边分成对,使得一对中的边相邻,并且每条边必须恰好包含在一对中。

例如,该图显示了 Chris 切割图形的一种方法。第一个示例测试包含该图的描述。

你有机会与克里斯竞争。找到一种方法来切割给定的图形或确定这是不可能的!

输入

输入的第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105)、图中的顶点数和边数。接下来的 m 行包含图边的描述。第 i 行包含两个空格分隔的整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),即第 i 条边连接的顶点的数量。保证给定的图是简单的(没有自环和多边)并且连通。

注意:由于输入和输出的大小可能非常大,因此请勿在您的语言中使用慢速输出技术。例如,不要在 C++ 中使用输入和输出流(cin、cout)。

输出

如果可以将给定图切割成长度为 2 的边不同路径,则输出 $$\frac{m}{2}$$ 线。在第 i 行中打印三个空格分隔的整数 xi、yi 和 zi,即第 i 条路径的描述。该图应包含此路径,即该图应包含边 (xi, yi) 和 (yi, zi)。每条边应该恰好出现在一条长度为 2 的路径中。如果有多个解,则输出其中任何一个。

如果无法切割给定的图形,则打印“无解”(不带引号)。

示例

输入 #1

8 12
1 2
2 3
3 4
4 1
1 3
2 4
3 5
3 6
5 6
6 7
6 8
7 8

输出 #1

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

输入 #2

3 3
1 2
2 3
3 1

输出 #2

No solution

输入 #3

3 2
1 2
2 3

输出 #3

1 2 3