버스 노선표의 자리 교환

문제

한 마을에서 임시 버스 노선을 운영하기 위해 정류장 방문 순서를 정리하고 있다. 노선에는 N개의 정류장이 있으며 각 정류장에는 1번부터 N번까지 서로 다른 식별 번호가 붙어 있다. 버스는 노선표에 적힌 첫 번째 정류장에서 출발하여 마지막 정류장까지 차례대로 방문한다. 처음 주어진 노선표에는 모든 정류장이 정확히 한 번씩 등장한다. 운영 담당자는 도로 사정을 반영하기 위해 노선표 수정 요청을 순서대로 처리한다. 각 요청에는 정류장 번호 두 개 a와 b가 적혀 있다. 이 요청은 현재 노선표에서 a번 정류장과 b번 정류장이 차지하고 있는 자리를 서로 교환하라는 뜻이다. 요청에 적힌 수는 노선표의 몇 번째 자리인지를 나타내는 수가 아니라 정류장 자체의 식별 번호이다. 두 정류장의 사이에 있는 다른 정류장들의 자리는 바뀌지 않는다. 교환은 두 정류장이 현재 어느 자리에 있는지를 기준으로 수행하며, 앞서 처리한 요청의 결과를 다음 요청에서도 그대로 사용한다. 예를 들어 어떤 정류장이 앞선 요청으로 마지막 자리로 이동했다면, 다음 요청에서는 그 정류장이 마지막 자리에 있는 상태에서 교환한다. 같은 정류장 번호가 여러 요청에 반복해서 등장할 수도 있다. a와 b가 같으면 같은 정류장을 자기 자신과 교환하므로 노선표는 바뀌지 않는다. 이 경우도 정상적인 요청 하나로 처리한다. 수정 요청으로 정류장이 추가되거나 삭제되는 일은 없으며, 모든 요청을 처리한 뒤에도 각 정류장은 정확히 한 번씩 등장한다. 수정 요청이 하나도 없을 수도 있다. 처음 노선표와 모든 수정 요청이 주어질 때, 요청을 주어진 순서대로 적용한 최종 정류장 방문 순서를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정류장 수 N과 수정 요청 수 Q가 주어진다. 두 수는 정수이며 1 ≤ N ≤ 20,000, 0 ≤ Q ≤ 20,000이다.
둘째 줄에 처음 노선표를 나타내는 N개의 정수가 방문 순서대로 주어진다. 이는 1부터 N까지의 순열이다.
다음 Q개 줄에 정류장 번호 a와 b가 주어진다. a와 b는 정수이며 1 ≤ a, b ≤ N이다.

출력

모든 요청을 처리한 최종 노선표의 정류장 번호 N개를 방문 순서대로 공백으로 구분하여 한 줄에 출력한다.

5 3
4 1 5 2 3
1 3
4 1
5 5

1 3 5 2 4

3 0
2 3 1

2 3 1

4 2
1 2 3 4
1 4
1 2

4 1 3 2

출처: Devin.KR 자체 제작