The kingdom

Bytetoria has $n$ cities and an even number of bidirectional roads. The road network lets you travel between any two cities of the kingdom.

King Byte loves even numbers. When he learned that some cities have an odd number of roads leaving them, he ordered the network expanded at once.

The advisor knows the treasury well. A project of that size would make the Winter Olympic Games, which the people await, impossible to hold. He plans to convince the king that Bytetoria already has enough even properties, and to ask that the work wait until next year.

First he will surprise the king with the fact that the number of odd-degree cities is even. Then he will pair those cities and, for each pair $(u, v)$, choose a route from $u$ to $v$ that uses an even number of roads. A route does not use the same road twice. Distinct routes do not share a road. A route may visit the same city more than once.

The advisor is sure this will convince the king. He cannot pick the routes himself, so he asks you for help.

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 250000$). They are the number of cities and the number of roads. $m$ is even.

Each of the next $m$ lines contains two integers $a$, $b$ ($1 \le a, b \le n$, $a \ne b$), meaning a bidirectional road between cities $a$ and $b$. At most one road joins any pair of cities.

You may assume that at least one city has odd degree.

Let $k$ be the number of odd-degree cities. $k$ is even.

If no set of routes matches the advisor's plan, print NIE on a single line.

Otherwise print $k/2$ routes, uniquely determined as follows.

Build a depth-first spanning tree from city $1$, always expanding the unused adjacent city of smallest index. Split each city $x$ into copies $x_0$ and $x_1$, and add a dummy city $0$. Move each original road onto a pair of copies:

When the search at city $x$ sees a road to an already visited city $y$ whose visit time is smaller than that of $x$, put that road between $x_1$ and $y_0$. After the subtree of a tree child $c$ of parent $p$ is finished, if the number of roads already incident to $c_1$ is odd, put the tree road between $c_1$ and $p_0$; if that number is even, put it between $c_0$ and $p_1$.

For every odd-degree city $u$, add a dummy road between $0$ and $u_0$. Find an Euler circuit of this new graph that starts at $0$. Whenever several unused incident roads remain, take the one with the smallest original index. Dummy roads have index $-1$; if those tie, take the one whose other endpoint has the smaller city index.

Removing the dummy roads from the circuit leaves $k/2$ even-length trails. Print them in circuit order.

Each route uses two lines. The first line has the start city $u_i$, the end city $v_i$, and the number of roads $l_i$, where $l_i$ is even. The second line has $l_i$ road indices in order along the route. Roads are numbered from $1$ to $m$ in input order.