ДОЛИНАТА НА МЕКСИКО

Град Мексико Сити е построен в красива долина, в която преди много векове е имало езеро. Някъде около 1300 г. жреците на Ацтеките решили да бъде засипана с пръст средата на езерото и там да бъде построена столицата на империята. Днес цялото езеро е засипано. 

Преди Ацтеките да дойдат, на брега около езерото били разположени c града. Някои от тези градове сключили помежду си търговски договори. Стоките се превозвали по езерото с кораби между градове със сключени търговски договори. Всеки два града могат да бъдат свързани с праволинейна отсечка през езерото.

Веднъж вождовете на градовете решили да въведат ред в търговията, като организират търговски път, свързващ всички градове около езерото. Пътят трябва да удовлетворява следните изисквания:
•	Може да започва от произволен град, трябва да минава през всеки от градовете около езерото и да завършва в град, различен от началния.
•	Пътят минава през всеки от градовете еднократно.
•	Между всеки два последователни града от пътя трябва да има сключен търговски договор. 
•	Всеки два последователни града по пътя са свързани с праволинейна отсечка. 
•	За да не стават катастрофи с корабите, пътят не трябва да се самопресича. 

Фигурата показва езерото и градовете около него. Отсечките (тънки и дебели) представят наличието на търговски договор между два града. Дебелата начупена линия представлява път, който удовлетворява условията на задачата. Пътят започва в град 2 и завършва в град 5. 

Посоченият път не се самопресича. Например редицата от върхове 2–6–5–1 не може да бъде част от път, защото се самопресича. 

Градовете около езерото са номерирани с числата от 1 до c по посока на часовниковата стрелка.

ЗАДАЧА
Напишете програма, която по дадени броя на градовете и двойките градове, между които има сключени търговски договори, построява път, удовлетворяващ горните изисквания.

ОГРАНИЧЕНИЯ
3 ≤ c ≤ 1000		Броят на градовете.

ВХОД

Програмата трябва да прочете следните данни от файла mexico.in
 
mexico.in	ОПИСАНИЕ	
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7	Ред 1: Съдържа цялото число c
Ред 2: Съдържа цяло число n, задаващо броя на договорите.
Следващите n реда: Всеки ред задава по един търговски договор и съдържа две цели числа, разделени с интервал. Те представят двата града, между които е сключен договор.	

ИЗХОД

Програмата трябва да изведе следните данни във файла mexico.out

Mexico.out	ОПИСАНИЕ	
2
3
4
1
7
6
5	Ако е възможно да се намери търсения път, изведете c реда, всеки съдържащ по едно цяло число. Числата трябва да показват последователността, в която да се посещават градовете.
Ако не е възможно да се намери търсения път, изведете единствен ред, съдържащ числото –1. 

ЗАБЕЛЕЖКА: Ако съществува повече от един път, който е решение на задачата, изведете кой да е от тях.

ОЦЕНЯВАНЕ
За част от тестове, които осигуряват общо 40 точки, е изпълнено 3 ≤ c ≤ 20.