Senior Postmen

It is the year 2036 and Europe is crowded with senior citizens. To keep them healthy, the European ministry for majority groups (seniors are a majority) suggests that they deliver the small amount of paper mail that is still being sent, usually to seniors. The suggestion is going to be implemented all over Europe.

The ministry devised a "senior postmen system" in the following way. Europe is divided into mail districts. A mail district has a street network of streets and junctions, and every street can be walked in both directions. In each district, arbitrarily many senior citizens are available to be hired as mailmen. Every morning each mailman receives a bag with mail to be delivered on a tour that covers a part of the street network. Every tour must satisfy the three conditions below, and such a tour is called senior compatible.

• It starts at a junction and ends at that same junction.
• It never passes a junction more than once. The seniors shall not be confused.
• It has no street in common with any other tour, so every street in the district is served by exactly one mailman. The seniors shall not fight with each other.

Together the tours must cover the network: every street belongs to exactly one tour.

Given the street network of a mail district, write a program that computes a set of senior compatible tours covering the network.

The input describes the street network.

The first line contains two integers $N$ and $M$ ($3 \le N \le 50\,000$, $3 \le M \le 50\,000$), the number of junctions and the number of streets. Junctions are numbered from 1 to $N$.

Each of the following $M$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$), meaning that a street connects junctions $u$ and $v$.

Every input satisfies the following.

1. Two junctions are connected by at most one street.
2. From any junction you can reach every other junction by walking along one or more streets.
3. A solution exists, that is, a set of senior compatible tours covering the network can be computed.

More than one set of tours can cover the network, so print only the one that the procedure below produces.

At each junction, consider the neighboring junctions in increasing order of number. At the start every street is unused and the stack holds junction 1 alone. Repeat the following until the stack is empty.

• Let $v$ be the junction on top of the stack.
• If $v$ still has an unused street, let $u$ be the smallest-numbered junction that an unused street leads to from $v$, and mark the street between $v$ and $u$ as used. If $u$ is not on the stack, push $u$ onto the stack. If $u$ is already on the stack, print $u$ and the junctions stacked above it on one line, from the lowest to the highest, then remove from the stack every junction above $u$. The junction $u$ stays on the stack.
• If $v$ has no unused street, then $v$ is the only junction on the stack. Remove $v$. If no unused street is left anywhere, stop. Otherwise put the smallest-numbered junction that still has an unused street on the stack by itself and continue.

Each printed line is one senior compatible tour. On a line, write the junction numbers in the order the mailman passes them, separated by one space, with the junction where the tour starts and ends written first and only once. Print the lines in the order the procedure produces them.

Because a solution exists, every junction has even degree.

While the procedure runs, the junctions $x_0, x_1, \dots, x_k$ on the stack are pairwise different and the street joining two neighboring ones is already used. So in the graph of unused streets only $x_0$ and $x_k$ have odd degree when $k \ge 1$. An odd degree is not zero, so as long as the stack holds two or more junctions the top junction $x_k$ still has a street to leave by. The procedure never gets stuck in the middle, and it starts over only when the stack has shrunk to a single junction.

A tour contains at least three junctions, because two junctions are connected by at most one street.