세탁소 옷걸이 자리 바꾸기

문제

한 세탁소에는 옷걸이를 하나씩 걸 수 있는 자리가 일렬로 N개 놓여 있다. 자리는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, 자리 번호는 작업 중에 바뀌지 않는다. 각 옷걸이에도 서로 다른 정수 번호가 적혀 있다. 작업을 시작할 때는 i번 자리에 i번 옷걸이가 걸려 있다. 따라서 처음에는 왼쪽부터 옷걸이 번호가 1, 2, …, N 순서로 보인다. 직원은 정리 작업을 하면서 두 자리를 지정하고, 그 두 자리에 걸린 옷걸이의 위치를 서로 바꾼다. 작업 지시에는 두 자리 번호 A와 B가 적혀 있다. 이 지시를 수행하면 A번 자리에 있던 옷걸이는 B번 자리로 이동하고, B번 자리에 있던 옷걸이는 A번 자리로 이동한다. 다른 자리에 걸린 옷걸이는 움직이지 않는다. 두 자리 번호가 같으면 아무 변화도 일어나지 않는다. 작업 지시는 모두 K개이며, 입력에 적힌 순서대로 하나씩 수행한다. 각 지시에 적힌 번호는 옷걸이 번호가 아니라 고정된 자리 번호이다. 따라서 앞선 작업으로 옷걸이가 이동했다면, 다음 작업에서는 이동한 뒤의 상태를 기준으로 두 자리의 옷걸이를 바꾼다. 같은 자리가 여러 지시에 등장할 수 있고, 같은 지시가 반복될 수도 있다. 작업 중 옷걸이가 추가되거나 사라지는 일은 없다. 모든 자리에는 항상 옷걸이가 정확히 하나씩 걸려 있고, 옷걸이 번호도 중복되지 않는다. 작업 지시가 하나도 없다면 처음 상태가 그대로 최종 상태가 된다. 모든 작업을 마친 뒤 손님에게 옷을 찾아주기 위해 현재 배치를 기록하려 한다. 왼쪽 자리부터 오른쪽 자리까지 차례대로 보이는 옷걸이 번호를 구한다. 번호가 작은 옷걸이부터 정렬하는 작업은 수행하지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ K ≤ 1,000이다.
다음 K개 줄에는 각 작업 지시의 자리 번호인 정수 A와 B가 공백으로 구분되어 주어진다. 1 ≤ A, B ≤ N이다. A와 B가 같을 수도 있다.

출력

모든 작업을 마친 뒤 1번 자리부터 N번 자리까지 걸려 있는 옷걸이 번호를 순서대로 공백으로 구분하여 한 줄에 출력한다. K가 0이면 처음 배치를 출력한다.

5 3
1 4
2 4
3 3

4 1 3 2 5

1 2
1 1
1 1

1

4 0

1 2 3 4

출처: Devin.KR 자체 제작