영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once.
Input
The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,…,n, and the post office is located at crossing 1.
After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets.
Every street is between two different crossings, and there is at most one street between two crossings.
Output
Print all the crossings on the route in the order you will visit them. You can print any valid solution.
If there are no solutions, print "IMPOSSIBLE".
Constraints
2 ≤ n ≤ 10^5 1 ≤ m ≤ 2 · 10^5 1 ≤ a,b ≤ n
예제
예제 1
6 8 1 2 1 3 2 3 2 4 2 6 3 5 3 6 4 5
1 2 6 3 2 4 5 3 1