In Bytetoria there are $n$ cities and even number of bidirectional roads connecting the cities. The road network allows commuting between any two cities of the kingdom.

King Bythor, the ruler of Bytetoria, is known for his passion for even numbers. When he realized that there are cities in his kingdom, which are a starting point of an odd number of roads leading out, he immediately demanded the expansion of the road network.

King's Adviser knows the Bytetoria finances well, and knows that the implementation of such a serious investment would make organization of the Winter Olympic Games impossible, very much expected by the Bytetorian people. He plans to convince the King that Bytetoria has enough “even” values in order to ask for a postponement of investment decision until the next year.

Firstly, the advisor would surprise the king by the fact that there is an even number of cities in Bytetoria with an odd number of outgoing roads. Then he plans to divide these cities into pairs, and for each of such created pairs $(u,v)$ assign the route from $u$ to $v$, consisting of an even number of roads. To further impress the king, no road would appear more than once on the way from $u$ to $v$. Furthermore, no Bytetorian road will be included in more than one of the designated routes.

The advisor is certain that such argumentation will convince the king. However, he is unable to cope with the actual routes design, so he asked you for help.

Input

The first line of input contains two integers $n$ and $m$ ($2 \leq n, m \leq 250\,000$). They denote the number of cities and the number of roads in Byteoria, respectively. $m$ is an even number.

Each of the subsequent $m$ lines contains two integers $a, b$ ($1\leq a,b \leq n$, $a\neq b$) indicating that the cities $a$ and $b$ are connected by a bidirectional road. Between any two cities there exists not more than one road.

It can be assumed that there exists a city, which is a staring point to an odd number of roads.

Output Format

By $k$ we denote the number of cities which are a staring point to the odd number of roads (the advisor is certain that $k$ is an even number).

If it is not possible to determine routes according to adviser's plan, the only line of output should contain the word NIE (Polish for no).

Otherwise, the program should output $\frac{k}{2}$ descriptions of designated routes. Each of the route's descriptions should consist of two lines.

The first line of $i$-th description should contain three integers $u_i$, $v_i$, $l_i$ ($2\mid l_i$) indicating that the route begins at city $u_i$, ends at city $v_i$ and consists of $l_i$ roads.

The second line of $i$-th description should contain $l_i$ integers denoting the numbers of the consecutive roads on the route.

The roads are numbered from $1$ to $m$, according to the order in which they were given at input.

In case there are multiple solutions, your program can output any one of them.

Examples

Input

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

Output

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