[AdditionalFile5645.zip](file://AdditionalFile5645.zip?type=additional_file)

#5645. 「PA 2014 Final」Królestwo

标签: 传统 | 时间限制: 3000 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Final Królestwo

在比特托邦（Bajtorii）有 $n$ 个城市和偶数条双向道路连接。王国的道路网保证了任意两个城市之间都是连通的。

比特托邦的统治者拜托尔国王以热爱偶数而闻名。当他意识到他的王国中存在一些发出奇数条道路的城市时，他立即要求扩建道路网。

国王的顾问非常了解比特托邦的财政状况，他深知实现如此大规模的投资将导致无法举办对比特托邦人民而言意义非凡的冬奥会。因此，他计划说服国王，证明比特托邦已经拥有足够多的「偶数」特质，并请求将投资推迟到明年。

首先，顾问将用比特托邦存在偶数个发出奇数条道路的城市（即度数为奇数的城市）这一事实来让国王感到惊讶。接着，他将把这些城市两两配对，并为每一对 $(u, v)$ 确定一条从 $u$ 到 $v$ 的路径，且该路径由偶数条道路组成。为了让国王更加惊叹，每条道路在同一条路径中不会出现超过一次。此外，比特托邦的任何一条道路在整套方案中都不会出现在超过一条路径中（即各条路径之间边不相交）。

顾问确信这些论据能够说服国王。然而，他无法独立完成这些路径的具体划分，因此他请求你的帮助。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n, m \leq 250000)$，分别表示城市数量和道路数量。$m$ 是一个偶数。

接下来的 $m$ 行，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示城市 $a$ 和 $b$ 之间由一条双向道路相连。任意两个城市之间最多只存在一条道路。

保证图中至少存在一个度数为奇数的城市。

输出格式

令 $k$ 为度数为奇数的城市数量（顾问确信 $k$ 是一个偶数）。

如果无法按照顾问的计划确定路径，则在输出一行 NIE。

否则，输出 $\frac{k}{2}$ 组路径描述。每组路径描述应包含两行：

• 第一行包含三个整数 $u_{i}, v_{i}, l_{i}$，表示该路径以 $u_{i}$ 为起点，以 $v_{i}$ 为终点，且由 $l_{i}$ 条道路组成（$l_{i}$ 必须为偶数）。
• 第二行包含 $l_{i}$ 个整数，表示该路径上按顺序排列的道路编号。道路按输入中出现的顺序从 $1$ 到 $m$ 编号。

如果存在多个解，你的程序可以输出其中任意一个。

样例

输入

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

输出

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