주차 구역 표지판 교환

문제

한 주차장은 일렬로 놓인 N개의 주차 구역을 운영한다. 구역의 위치에는 왼쪽부터 1번부터 N번까지 고정된 번호가 붙어 있다. 각 위치에는 이용자가 구역을 구분할 수 있도록 이동식 표지판이 하나씩 놓여 있다. 위치 번호는 바뀌지 않지만 표지판은 다른 위치로 옮길 수 있다. 각 표지판에는 양의 정수 하나가 적혀 있다. 서로 다른 표지판에 같은 정수가 적혀 있을 수도 있다. 주차장 관리자는 다음 날의 구역 배치를 준비하기 위해 두 위치에 놓인 표지판을 서로 교환하는 작업을 여러 번 수행한다. 한 번의 작업에는 두 위치 번호 a와 b가 주어진다. 교환 작업을 수행하면 a번 위치에 있던 표지판은 b번 위치로 옮겨지고, b번 위치에 있던 표지판은 a번 위치로 옮겨진다. 다른 위치의 표지판은 움직이지 않는다. a와 b가 같은 경우도 주어질 수 있으며, 이때는 모든 표지판이 그대로 남는다. 같은 두 위치를 여러 번 교환하는 작업도 허용한다. 작업은 입력에 주어진 순서대로 수행한다. 뒤의 작업은 앞의 작업을 모두 마친 상태를 기준으로 한다. 예를 들어 1번 위치와 3번 위치를 교환한 뒤 1번 위치와 2번 위치를 교환하면, 두 번째 작업에서 이동하는 것은 첫 번째 교환을 마친 뒤 1번 위치에 놓인 표지판이다. 처음 1번 위치에 있던 표지판을 따로 찾아서 옮기는 것이 아니다. 처음 각 위치에 놓인 표지판의 정수와 관리자가 수행할 교환 작업이 주어진다. 모든 작업을 마친 뒤 각 위치에 놓인 표지판의 정수를 왼쪽부터 순서대로 구한다. 작업이 하나도 주어지지 않을 수도 있으며, 이 경우에는 처음 배치를 그대로 출력한다. 같은 정수가 여러 번 나타나더라도 각 위치의 값을 빠짐없이 출력해야 한다.

입력

첫째 줄에 정수 N과 M이 공백으로 구분되어 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ M ≤ 1,000이다. 둘째 줄에 처음 각 위치에 놓인 표지판의 정수 N개가 주어진다. 각 정수는 1 이상 1,000 이하이다. 다음 M개 줄에는 교환할 두 위치 번호 a와 b가 주어진다. a와 b는 1 이상 N 이하의 정수이며 서로 같을 수도 있다.

출력

모든 교환 작업을 마친 뒤, 1번 위치부터 N번 위치까지 표지판에 적힌 정수를 공백으로 구분하여 한 줄에 출력한다.

5 3
11 22 33 44 55
1 5
2 4
1 2

44 55 33 22 11

3 0
8 8 2

8 8 2

1 2
9
1 1
1 1

9

출처: Devin.KR 자체 제작