옷걸이 순서 변경

문제

세탁소에는 포장을 마친 옷을 걸어 두는 긴 레일이 있다. 레일에는 서로 다른 번호가 붙은 옷걸이 N개가 있으며, 처음에는 왼쪽부터 1번, 2번, …, N번 순서로 놓여 있다. 직원은 손님의 방문 순서가 바뀔 때마다 특정 옷걸이 하나를 다른 옷걸이 바로 오른쪽으로 옮긴다. 모든 변경이 끝난 뒤 포장 담당자가 확인할 최종 순서를 구하려고 한다. 변경 지시 하나는 서로 다른 두 옷걸이 번호 x와 y로 주어진다. 직원은 현재 위치에서 x번 옷걸이를 빼낸 다음, 현재 y번 옷걸이의 바로 오른쪽에 끼운다. x번을 빼낸 자리는 주변 옷걸이가 이어지면서 사라진다. y번이 가장 오른쪽에 있었다면 x번이 새로운 가장 오른쪽 옷걸이가 된다. x번이 이미 y번 바로 오른쪽에 있다면 순서는 달라지지 않는다. 지시는 입력된 순서대로 하나씩 적용한다. 각 지시에 등장하는 번호는 최초에 부여한 옷걸이 번호이며, 현재 왼쪽에서 몇 번째인지 나타내는 위치 번호가 아니다. 옷걸이를 옮겨도 번호는 바뀌지 않고, 새 옷걸이를 추가하거나 기존 옷걸이를 없애는 일도 없다. 따라서 모든 시점에 1번부터 N번까지의 옷걸이가 정확히 하나씩 존재한다. 예를 들어 현재 순서가 1, 2, 3, 4일 때 2번을 4번 바로 오른쪽으로 옮기면 1, 3, 4, 2가 된다. 이후의 지시는 이렇게 바뀐 순서에 적용한다. 변경 지시가 한 개도 없을 수도 있으며, 이때는 처음 순서가 그대로 최종 순서이다. 주어진 모든 지시를 처리한 뒤 레일의 왼쪽부터 오른쪽까지 옷걸이 번호를 출력하는 프로그램을 작성한다.

입력

첫째 줄에 옷걸이 수 N과 변경 지시 수 M이 주어진다. 2 ≤ N ≤ 15,000, 0 ≤ M ≤ 15,000이다.
다음 M개 줄에 정수 x와 y가 주어진다. 1 ≤ x, y ≤ N이고 x ≠ y이다.

출력

모든 변경을 적용한 최종 옷걸이 번호 N개를 왼쪽부터 순서대로 공백으로 구분하여 한 줄에 출력한다.

5 3
2 4
1 2
5 3

3 5 4 2 1

4 2
2 1
1 4

2 3 4 1

2 0

1 2

출처: Devin.KR 자체 제작