Messengers

The kingdom of Byteland has $n$ cities numbered $1$ through $n$ (with $3 \le n \le 500$); city $1$ is the capital. Cities are joined by two-way roads, and there is at most one direct road between any pair of cities. The road network is 2-connected: for any two different cities $A$ and $B$ one can travel from $A$ to $B$ and back to $A$ without passing through any city of the first leg a second time. Equivalently, between any two cities there are two routes that share no intermediate city.

The king sends two messengers to warn every city of an approaching attack. Both messengers set out from the capital. A messenger walks along the roads and may pass through the same city several times, but the order in which he reaches cities for the first time must follow a plan fixed in advance.

A plan is a sequence of all $n$ cities $x_1, x_2, \dots, x_n$ (a permutation of $1..n$) with $x_1 = 1$. When moving from $x_i$ to $x_{i+1}$ the messenger may travel only through cities he has already visited, so $x_{i+1}$ must be directly connected by a road to at least one of $x_1, \dots, x_i$.

The enemy has secretly occupied exactly one city, and it is not the capital. As soon as a messenger reaches the occupied city he delivers his warning there and is then captured, so he makes no further moves. The two plans must be chosen so that, whichever non-capital city turns out to be occupied, every city is warned by at least one of the messengers (the occupied city counts as warned by the messenger who is captured there).

The first line contains one integer $n$, the number of cities. The second line contains one integer $d$, the number of roads. Each of the next $d$ lines contains two different integers $a$ and $b$ ($1 \le a, b \le n$), describing a road that directly connects cities $a$ and $b$. Every road is listed exactly once.

Print two plans, one per line. Each plan is written as $n$ city numbers separated by single spaces; the first line is the first messenger's plan and the second line is the second messenger's plan. Both plans begin at the capital (city $1$) and must satisfy all the conditions above for every possible occupied city.

Several pairs of plans may satisfy the conditions. Print the lexicographically smallest valid pair: among all valid pairs pick the one whose first line, read as a sequence of city numbers, is lexicographically smallest; if more than one pair shares that first line, pick the one whose second line is lexicographically smallest.