The Valley of Mexico

Mexico City sits in a beautiful valley known as the Valley of Mexico, which long ago was mostly a lake. Around the year 1300, Aztec religious leaders decreed that the center of the lake be filled in to build the capital of their empire. Today the lake is completely covered.

Before the Aztecs arrived, $c$ cities stood on the shores around the lake. Some of these cities had commercial agreements with one another. Goods were traded by boat between any two cities that shared an agreement, and any two cities could be joined by a straight line segment drawn across the lake.

The kings eventually organized this commerce into a single commerce route that connected every city around the lake. The route had to satisfy all of the following:

• It could start in any city, but had to end in a city different from the start.
• It visited every city exactly once.
• Every two consecutively visited cities shared a commercial agreement.
• Every two consecutively visited cities were joined by a line segment across the lake.
• To keep the boats from colliding, the route never crossed itself.

In the figure the lines (both thick and thin) are commercial agreements; the thick lines form a commerce route that starts at city 2 and ends at city 5, and this route never crosses itself. A route such as $2 \to 6 \to 5 \to 1$ would be illegal, because it would cross itself.

The cities are numbered $1$ through $c$ in clockwise order around the lake.

Given $c$ and the list of commercial agreements, construct a commerce route that meets every requirement above.

• Line 1: the integer $c$.
• Line 2: an integer $n$, the number of commercial agreements.
• Next $n$ lines: each contains two space-separated integers, the two cities joined by one commercial agreement. Each agreement is listed once and is undirected.

Several different commerce routes may satisfy every requirement (in particular, a route and its reverse are both valid). Output the lexicographically smallest one.

Read a route as the sequence of city numbers in the order they are visited. Route $A$ is smaller than route $B$ if, at the first position where they differ, $A$ has the smaller city number. Print the chosen route on $c$ lines, the $i$-th line holding the $i$-th city visited.

If no commerce route satisfies every requirement, print a single line containing $-1$.

• $3 \le c \le 1000$ — the number of cities around the lake.