小克里斯正在参加切图比赛。他是一名职业选手。考验他能力的时刻到了。
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