문제
때는 2036년, 유럽의 노인 인구는 급증하였다.
그들의 건강 관리를 위해, 유럽 내각의 과반수는 노인들이 노인들에게 보내진 종이 편지를 직접 배달하도록 하는 것을 제안했다.
이 제안은 유럽 전체에서 시행되었다.
유럽 내각은 다음과 같은 방식으로 "우편 시스템"을 고안했다. 유럽은 여러 우편 지역으로 나뉘어져 있다.
각 우편 지역은 교차로와 두 교차로를 잇는 길로 구성된 네트워크로 표현된다. 모든 길은 양방향 통행이 가능하다.
각 지역에 고용될 수 있는 노인의 수에는 제한이 없다.
매일 아침, 각 우편 배달원은 네트워크의 일부를 지나는 노선에 배달 할 우편물이 담긴 가방을 받는다.
모든 배달 노선은 노인들이 힘들지 않도록 다음 조건을 충족해야 한다.
동일한 교차로에서 시작하고 끝난다.
같은 교차로를 두 번 이상 통과하지 않는다. (노인들은 길을 헷갈릴 수 있다.)
다른 노선과 겹치는 거리가 없어야 한다. 따라서, 지역 내 모든 거리는 정확히 한 명의 우체부가 제공해야 한다.
(노인들은 서로 싸우지 않아야 한다.)
모든 노선은 네트워크를 덮어야 한다: 네트워크의 각 길은 정확히 하나의 노선에 포함되어야 한다.
유럽 내각은 우편 지역의 네트워크가 주어졌을 때, 위의 조건을 만족하도록 노선을 정하는 소프트웨어를 필요로 한다.
입력
입력은 네트워크를 의미한다.
첫 줄에는 교차로의 개수 N과, 길의 개수 M이 주어진다. (3 ≤ N, M ≤ 500,000)
다음 M개의 줄에는 u, v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 이는 u번째 교차로와 v번째 교차로를 잇는 길이 있다는 뜻이다.
입력은 다음과 같은 조건을 만족한다.
두 교차로를 잇는 길은 최대 하나이다.
어떤 교차로에서도 하나 이상의 길을 사용하여 다른 임의의 교차로로 이동할 수 있다.
위의 조건을 만족하는 노선으로 분할되는 경우만 입력으로 주어진다.
출력
각 줄은 하나의 노선을 의미한다. 노선을 이루는 교차로를 순서대로 출력한다.
조건을 만족하는 답이 여러개인 경우, 아무거나 하나 출력하면 된다.
예제1
1015
13
51
23
92
34
63
45
74
48
57
85
67
78
810
109
23458109
784
15763