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

Before the Aztecs arrived, c cities were located around the lake on its shores. Some of these cities established commercial agreements. Goods were traded, using boats, between cities that had a commercial agreement. It was possible to connect any two cities by a line segment through the lake.

Eventually, the kings of the cities decided to organize this commerce. They designed a commerce route that connected every city around the lake. The route met the following requirements:

• It could start in any of the cities, visited each of the cities around the lake, and finally ended in another city different from the starting city.
• . The route visited each city exactly once.
• . Every pair of consecutively visited cities in the route had a commercial agreement.
• . Every pair of consecutively visited cities in the route was connected by a line segment.
• . To avoid crashes between boats, the route never crossed itself.

This route never crosses itself. It would not be legal, for example, to construct a route that went from 2 to 6 to 5 to 1, since the route would cross itself. Cities in the lake are numbered from 1 through c moving in clockwise direction.

TASK

CONSTRAINTS

입력

• LINE 1: Contains integer c
• LINE 2: Contains an integer n that represents the number of commercial agreements
• NEXT n LINES: Each line represents a unique commercial agreement. Every line contains two space-separated integers that represent the two cities involved in the agreement.

출력

If it’s possible to construct the commerce route, write c lines, each with an integer that represents the order in which the cities are visited in the commerce route. If it’s not possible to construct a commerce route that meets all the requirements, output a single line containing the number -1.

NOTE: If there is more than one commerce route that meets the requirements, any of them you output will be considered correct.

입출력 예

입력

7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

출력

2
3
4
1
7
6
5

출처: Mexico Official version IOI’06 English
special judge: august14