题目描述

你有一个无向连通图，边的总数为偶数。

设图中有 $k$ 个奇点（度数为奇数的点），你需要把它们配成 $k/2$ 个点对（显然 $k$ 被 $2$ 整除）。对于每个点对 $(u,v)$，你需要用一条长度为偶数（假设每条边长度为 $1$）的路径将 $u$ 和 $v$ 连接。每条路径允许经过重复的点，但不允许经过重复的边。这 $k/2$ 条路径之间也不能有重复的边。

输入格式

第一行有两个整数 $n,m$$(2≤n,m≤250000)$，分别表示点数、边数，$m$ 为偶数。 接下来 $m$ 行，每行两个整数 $a,b$$(1≤a,b≤n,a≠b)$，表示 $a,b$ 间连有一条边。不存在重边。保证奇点的数目不为零。

输出格式

如果你认为无解就输出 NIE。

设图中有 $k$ 个奇点，则输出由 $k/2$ 部分组成，每个部分包含两行：第一行为 $u,v,l$，表示连接的两个点，及路径长度。第二行为空格隔开的 $l$ 个整数，表示 $u$ 到 $v$ 的路径。边按照输入顺序从 $1$ 到 $m$ 编号。若有多组答案，任意输出其中一个。

输入样例

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

输出样例

样例输出：
1 5 2
6 5
2 4 2
8 4
另一种合法输出：
1 5 6
1 2 3 7 6 5
2 4 2
8 4

提示

鸣谢 Jcvb 提供题目。