공연장 좌석표 교환

문제

한 공연장은 무대 앞의 긴 좌석 줄을 단체 관람객에게 배정했다. 이 줄에는 N개의 좌석이 있으며, 무대를 바라보는 방향을 기준으로 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 관람객도 서로 구별되는 1번부터 N번까지의 번호를 하나씩 가지고 있다. 처음 좌석표를 만들었을 때는 i번 좌석에 i번 관람객이 배정되어 있다. 공연 준비 과정에서 좌석표를 여러 번 수정하게 되었다. 담당자는 수정 사항을 두 좌석 번호로 기록한다. 한 수정 사항에 적힌 번호가 a와 b라면, 그 시점에 a번 좌석과 b번 좌석에 배정되어 있는 두 관람객의 자리를 서로 바꾼다. 다른 좌석의 배정은 그 수정으로 바뀌지 않는다. 두 번호가 같을 수도 있으며, 이 경우에는 좌석표에 아무 변화도 일어나지 않는다. 수정 사항은 적힌 순서대로 하나씩 적용한다. 앞선 수정으로 자리가 바뀐 관람객도 뒤의 수정에서 다시 이동할 수 있다. 같은 두 좌석이 여러 번 등장할 수 있고, 한 관람객이 여러 차례 자리를 옮겨도 된다. 수정 사항의 두 숫자는 관람객 번호가 아니라 좌석 번호이므로, 항상 수정 직전의 좌석표를 기준으로 그 좌석에 있는 관람객을 확인해야 한다. 담당자가 원하는 결과는 모든 수정을 마친 뒤의 좌석표다. 결과는 관람객 번호순이 아니라 좌석 번호순으로 작성한다. 즉, 첫 번째 값은 최종적으로 1번 좌석에 배정된 관람객의 번호이고, 두 번째 값은 2번 좌석에 배정된 관람객의 번호다. 이러한 방식으로 N번 좌석까지 빠짐없이 적는다. 수정 사항이 하나도 없다면 처음 만든 좌석표가 그대로 최종 좌석표가 된다. 모든 수정은 두 배정의 교환이므로 빈 좌석이 생기거나 같은 관람객이 두 좌석에 배정되는 일은 없다. 좌석의 수와 수정 기록이 주어질 때 최종 좌석표를 구하는 프로그램을 작성한다.

입력

첫째 줄에 좌석 수 N과 수정 횟수 M이 공백으로 구분되어 주어진다. N과 M은 정수이며 1 ≤ N ≤ 100,000, 0 ≤ M ≤ 20,000이다.
다음 M개의 줄에는 한 수정 사항을 나타내는 정수 a와 b가 공백으로 구분되어 주어진다. 1 ≤ a, b ≤ N이다. 주어진 줄의 순서대로 수정을 적용한다.

출력

모든 수정을 적용한 뒤, 1번 좌석부터 N번 좌석까지 배정된 관람객 번호를 공백으로 구분하여 한 줄에 출력한다.

6 3
1 4
2 6
4 6

4 6 3 2 5 1

1 0

1

4 3
2 2
1 3
1 3

1 2 3 4

출처: Devin.KR 자체 제작