출발 대기 줄 바꾸기

문제

마을 마라톤 대회에서는 참가자가 출발선으로 이동하기 전에 한 줄로 서서 안내를 기다린다. 참가자는 모두 N명이며, 각 참가자는 1부터 N까지의 서로 다른 정수 하나를 배번호로 사용한다. 처음에는 배번호가 작은 참가자부터 차례로 줄을 서므로, 맨 앞부터 배번호가 1, 2, ..., N인 순서다. 줄의 위치에도 맨 앞부터 1번부터 N번까지 번호를 붙인다. 출발 준비 중에는 안내원의 지시에 따라 일부 참가자가 서로 자리를 바꾼다. 지시 하나에는 두 위치 번호 x와 y가 적혀 있다. 이 지시를 받으면 현재 x번 위치에 있는 참가자와 현재 y번 위치에 있는 참가자가 서로의 자리로 이동한다. 다른 위치에 있는 참가자는 움직이지 않으며, 줄 전체의 길이나 위치 번호도 바뀌지 않는다. x와 y가 같다면 같은 위치를 두 번 지정한 것이므로 아무 변화도 일어나지 않는다. 안내원은 이러한 지시를 모두 M개 전달한다. 지시는 입력에 적힌 순서대로 하나씩 적용하며, 앞선 지시로 바뀐 줄의 상태가 다음 지시의 기준이 된다. 특히 지시에 적힌 두 수는 참가자의 배번호가 아니라 줄에서의 위치 번호다. 같은 위치가 여러 지시에 등장할 수 있고, 같은 두 위치를 바꾸는 지시가 반복될 수도 있다. 어느 경우든 현재 그 위치에 서 있는 참가자를 확인하여 자리를 바꾼다. 모든 지시가 끝나면 진행 요원은 참가자가 출발선으로 이동할 순서를 확인하려 한다. 이를 위해 최종 대기 줄을 맨 앞에서 맨 뒤까지 읽었을 때 나타나는 배번호를 기록한다. 참가자가 중간에 줄을 떠나거나 새로 들어오는 일은 없으므로, 최종 기록에도 1부터 N까지의 배번호가 각각 한 번씩 나타난다. 지시가 하나도 없다면 처음 줄의 순서를 그대로 기록한다. 주어진 지시를 모두 적용한 뒤의 배번호 순서를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 다음 M개의 줄에는 각 지시의 위치 번호를 나타내는 정수 x와 y가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000, 0 ≤ M ≤ 1,000, 1 ≤ x, y ≤ N이다. M이 0이면 지시를 나타내는 줄은 주어지지 않는다.

출력

모든 지시를 적용한 뒤 맨 앞부터 맨 뒤까지의 참가자 배번호 N개를 공백으로 구분하여 한 줄에 출력한다.

5 3
1 4
2 5
4 5

4 5 3 2 1

3 2
2 2
1 3

3 2 1

4 0

1 2 3 4

출처: Devin.KR 자체 제작