在巴伊托里亚有 $n$ 个城市和偶数条连接城市的双向道路。道路网络允许在王国的任意两个城市之间通行。

巴伊托里亚的国王巴伊托尔以其对偶数的偏爱而闻名。当他发现王国中存在奇数条道路通向的城市时，他立即要求扩建道路网络。

国王的顾问对巴伊托里亚的财政状况了如指掌，他知道实施如此重大的投资将导致巴伊托里亚人民翘首以盼的冬季奥运会无法举办。因此，他计划说服国王，巴伊托里亚拥有足够多的“偶数”优点，并请求将投资推迟到明年。

首先，顾问将用巴伊托里亚存在偶数个城市拥有奇数条出路的道路这一事实来震惊国王。然后他将这些城市两两配对，对于每对形成的城市 ($u$, $v$)，他将规划一条从 $u$ 到 $v$ 的路线，该路线由偶数条道路组成。为了进一步让国王感到惊讶，任何道路在从 $u$ 到 $v$ 的路线上都不会出现超过一次。此外，巴伊托里亚的任何道路都不会属于多于一条已规划的路线。

顾问确信这些论点会说服国王。但他无法实际规划路线，因此他请求你提供帮助。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \leq n, m \leq 250\,000$)。它们分别表示巴伊托里亚的城市数量和道路数量。$m$ 是一个偶数。

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

可以假设存在一个城市，有奇数条道路通向它。

输出格式

设 $k$ 为有奇数条道路通向的城市数量（顾问确信 $k$ 是一个偶数）。

如果无法按照顾问的计划规划路线，则输出的唯一一行应为单词 NIE。

否则，应输出 $k/2$ 条已规划路线的描述。每条路线描述应由两行组成。第 $i$ 条描述的第一行应包含三个整数 $u_{i}$，$v_{i}$，$l_{i}$ ($2 \mid l_{i}$)，表示路线从 $u_{i}$ 开始，在 $v_{i}$ 结束，并由 $l_{i}$ 条道路组成。第 $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