시니어 집배원

2036년의 유럽은 노인이 다수다. 유럽 다수집단부는 노인의 건강을 지키려고, 아직 남아 있는 적은 양의 종이 우편물을 노인이 직접 배달하게 하자고 제안했다. 받는 사람도 대개 노인이다. 이 제안은 유럽 전역에서 시행된다.

부처가 만든 "시니어 집배원 제도"는 이렇다. 유럽은 여러 우편 구역으로 나뉜다. 한 우편 구역에는 거리와 교차로로 이루어진 도로망이 있고, 모든 거리는 양방향으로 걸을 수 있다. 각 구역에서 집배원으로 고용할 노인은 얼마든지 구할 수 있다. 매일 아침 집배원은 우편물이 든 가방을 받아 도로망의 일부를 도는 경로를 배달한다. 모든 경로는 다음 세 조건을 지켜야 하고, 이런 경로를 시니어 친화 경로라고 한다.

• 어떤 교차로에서 출발해 같은 교차로로 돌아온다.
• 어떤 교차로도 두 번 지나지 않는다. 노인이 헷갈리면 안 되기 때문이다.
• 다른 경로와 거리를 하나도 공유하지 않는다. 구역의 모든 거리는 정확히 한 집배원이 맡는다. 노인끼리 다투면 안 되기 때문이다.

경로를 모두 합치면 도로망을 덮어야 한다. 즉 도로망의 모든 거리가 정확히 하나의 경로에 들어간다.

우편 구역의 도로망이 주어질 때, 그 도로망을 덮는 시니어 친화 경로의 집합을 구하는 프로그램을 작성하라.

입력은 도로망을 나타낸다.

첫째 줄에 교차로의 수 $N$과 거리의 수 $M$이 주어진다 ($3 \le N \le 50\,000$, $3 \le M \le 50\,000$). 교차로에는 1부터 $N$까지 번호가 붙어 있다.

다음 $M$개 줄에는 각각 두 정수 $u$와 $v$가 주어진다 ($1 \le u, v \le N$, $u \ne v$). 교차로 $u$와 $v$를 잇는 거리가 있다는 뜻이다.

입력은 항상 다음을 만족한다.

1. 두 교차로를 잇는 거리는 많아야 하나다.
2. 어떤 교차로에서든 거리를 하나 이상 지나 다른 모든 교차로로 갈 수 있다.
3. 답이 존재한다. 즉 도로망을 덮는 시니어 친화 경로의 집합을 만들 수 있다.

도로망을 덮는 방법은 여러 가지일 수 있으므로, 다음 절차가 만드는 답 하나만 출력한다.

각 교차로에서 이웃한 교차로는 번호가 작은 쪽부터 본다. 처음에는 모든 거리가 사용하지 않은 상태이고, 스택에는 교차로 1만 들어 있다. 스택이 빌 때까지 아래를 반복한다.

• 스택의 맨 위에 있는 교차로를 $v$라 하자.
• $v$에 사용하지 않은 거리가 남아 있으면, 그 거리로 갈 수 있는 교차로 중 번호가 가장 작은 것을 $u$라 하고, $v$와 $u$를 잇는 거리를 사용한 것으로 표시한다. $u$가 스택에 없으면 $u$를 스택에 넣는다. $u$가 이미 스택에 있으면 $u$와 그 위에 쌓인 교차로를 아래에서 위 순서로 한 줄에 출력하고, $u$ 위에 쌓인 교차로를 모두 스택에서 뺀다. $u$는 스택에 남는다.
• $v$에 사용하지 않은 거리가 없으면 이때 스택에는 $v$ 하나만 남아 있다. $v$를 스택에서 뺀다. 사용하지 않은 거리가 하나도 없으면 멈춘다. 남아 있으면 사용하지 않은 거리가 있는 교차로 중 번호가 가장 작은 것을 스택에 혼자 넣고 계속한다.

출력한 각 줄이 시니어 친화 경로 하나다. 한 줄에는 집배원이 지나는 순서대로 교차로 번호를 공백 하나로 구분해 적고, 출발이자 도착인 교차로는 맨 앞에 한 번만 적는다. 줄의 순서는 절차가 출력한 순서를 그대로 따른다.

답이 존재한다는 조건에서 모든 교차로의 차수는 짝수다.

절차가 도는 동안 스택에 든 교차로 $x_0, x_1, \dots, x_k$는 서로 다르고, 이웃한 두 교차로를 잇는 거리는 이미 사용한 상태다. 그래서 사용하지 않은 거리만 남긴 그래프에서 차수가 홀수인 교차로는 $k \ge 1$일 때 $x_0$과 $x_k$뿐이다. 맨 위 교차로 $x_k$의 차수가 홀수이면 0이 아니므로, 스택에 교차로가 둘 이상 있는 동안에는 $x_k$에서 나갈 거리가 반드시 남아 있다. 즉 절차는 중간에 막히지 않고, 스택이 교차로 하나로 줄었을 때만 새로 시작한다.

한 경로에 들어가는 교차로는 최소 세 개다. 두 교차로를 잇는 거리가 많아야 하나이기 때문이다.