우편함 교환 기록

문제

한 우체국의 분류대에는 왼쪽부터 1번부터 N번까지 번호가 붙은 칸이 있다. 오늘 분류할 봉투도 정확히 N개이며, 각 봉투에는 서로 다른 정수 번호가 1번부터 N번까지 하나씩 붙어 있다. 업무를 시작할 때에는 i번 칸에 i번 봉투가 들어 있다. 칸의 번호는 분류대에 고정되어 있고, 봉투의 번호는 봉투를 따라 이동한다. 직원은 배달 순서를 맞추기 위해 두 칸의 봉투를 맞바꾸는 작업을 수행한다. 작업 기록에 두 정수 a와 b가 적혀 있으면, 그 작업을 시작하는 순간 a번 칸에 있던 봉투와 b번 칸에 있던 봉투를 서로 교환한다. 다른 칸의 봉투는 움직이지 않는다. 교환은 한 번의 작업으로 완료되므로 작업 도중의 상태를 따로 고려할 필요가 없다. 두 정수는 봉투 번호가 아니라 칸 번호를 뜻한다. 예를 들어 어떤 교환으로 1번 봉투가 다른 칸으로 이동했더라도, 다음 기록의 숫자 1은 여전히 분류대의 첫 번째 칸을 가리킨다. 따라서 각 기록은 앞선 작업을 모두 반영한 현재 배치를 기준으로 처리해야 한다. 두 칸 사이에 있는 봉투들의 순서를 뒤집거나 한 칸씩 밀어내는 작업은 수행하지 않는다. 한 기록에서 a와 b가 같을 수도 있다. 이때에는 같은 칸을 지정한 것이므로 배치가 바뀌지 않는다. 동일한 교환 기록이 여러 번 등장할 수도 있으며, 등장할 때마다 차례대로 작업을 수행한다. 교환 작업이 전혀 없을 수도 있다. 모든 작업에서 봉투를 두 칸 사이에 맞바꾸기만 하므로 각 칸에는 항상 정확히 한 개의 봉투가 들어 있다. 직원이 남긴 Q개의 교환 기록이 주어진다. 모든 기록을 순서대로 처리한 뒤, 분류대의 왼쪽 끝인 1번 칸부터 오른쪽 끝인 N번 칸까지 각 칸에 들어 있는 봉투 번호를 구해야 한다. 출력에서는 봉투가 지나온 경로나 이동 횟수를 표시하지 않고 마지막 배치만 표시한다.

입력

첫째 줄에 칸 수 N과 교환 횟수 Q가 공백으로 구분되어 주어진다. N은 1 이상 100,000 이하의 정수이고, Q는 0 이상 20,000 이하의 정수다.
다음 Q개 줄에 교환할 두 칸의 번호 a와 b가 주어진다. a와 b는 각각 1 이상 N 이하의 정수이며, 서로 같을 수도 있다.

출력

모든 교환을 마친 뒤 1번 칸부터 N번 칸까지 들어 있는 봉투 번호 N개를 공백으로 구분하여 한 줄에 출력한다.

5 3
1 4
2 4
3 3

4 1 3 2 5

1 0

1

4 4
1 4
1 4
2 3
2 3

1 2 3 4

출처: Devin.KR 자체 제작