반납대의 자리 교환

문제

도서관의 반납대에는 책을 한 권씩 놓을 수 있는 자리가 N개 있다. 자리는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 오늘 반납된 책에도 서로 다른 관리 번호가 붙어 있으며, 관리 번호는 1부터 N까지의 정수를 하나씩 사용한다. 처음에는 i번 자리에 관리 번호가 i인 책이 놓여 있다. 담당자는 반납된 책을 점검하면서 두 자리의 책을 맞바꾸는 작업을 한다. 작업 기록 한 줄에는 두 자리 번호 x와 y가 적혀 있다. 이 기록을 처리할 때는 현재 x번 자리에 놓인 책과 현재 y번 자리에 놓인 책을 서로 바꾼다. 두 번호는 책의 관리 번호가 아니라 반납대의 자리 번호를 뜻한다. 작업 기록은 작성된 순서대로 처리한다. 앞선 작업으로 책의 위치가 달라졌다면, 다음 작업은 달라진 상태를 기준으로 수행한다. 예를 들어 어떤 작업에서 1번 자리와 4번 자리의 책을 바꾼 뒤 다시 같은 두 자리를 바꾸면, 두 자리의 책은 첫 작업 전 위치로 돌아온다. 두 자리 번호가 같을 수도 있으며, 이 경우에는 어떤 책의 위치도 바뀌지 않는다. 모든 작업은 두 자리에 이미 놓여 있는 책만 맞바꾼다. 작업 도중 책을 추가하거나 없애지 않으며, 책이 없는 자리도 생기지 않는다. 따라서 어떤 시점에도 각 자리에는 정확히 한 권의 책이 있고, 각 관리 번호도 반납대 전체에 정확히 한 번 등장한다. 점검이 끝난 뒤 담당자는 왼쪽부터 책의 관리 번호를 읽어 최종 배치표를 작성하려 한다. 주어진 작업 기록 Q개를 모두 처리한 뒤, 1번 자리부터 N번 자리까지 놓인 책의 관리 번호를 순서대로 구한다. 작업 기록이 하나도 없다면 처음 배치를 그대로 사용한다.

입력

첫째 줄에 정수 N과 Q가 공백으로 주어진다. 다음 Q개 줄에는 각 작업의 자리 번호를 나타내는 정수 x와 y가 공백으로 주어진다. 작업은 입력된 순서대로 수행한다.
1 ≤ N ≤ 20,000
0 ≤ Q ≤ 20,000
1 ≤ x, y ≤ N

출력

모든 작업을 처리한 뒤 각 자리에 놓인 책의 관리 번호 N개를 1번 자리부터 순서대로 공백으로 구분하여 한 줄에 출력한다.

5 3
1 4
2 4
3 3

4 1 3 2 5

4 0

1 2 3 4

3 2
1 3
1 3

1 2 3

출처: Devin.KR 자체 제작