급식 쟁반 자리 바꾸기

문제

학교 급식실에서는 배식을 시작하기 전에 긴 받침대 위에 쟁반 N개를 한 줄로 놓는다. 받침대의 자리는 왼쪽부터 1번, 2번, …, N번이다. 각 쟁반에는 그 쟁반에 담을 식단의 번호가 하나 적혀 있다. 같은 식단을 담을 쟁반이 여러 개일 수 있으므로, 서로 다른 쟁반에 같은 번호가 적혀 있어도 된다. 처음 쟁반을 놓은 뒤 급식 담당자는 전달받은 작업표에 따라 쟁반의 위치를 바꾼다. 작업표의 각 줄에는 두 자리의 번호가 적혀 있다. 한 번의 작업에서는 그 두 자리에 현재 놓여 있는 쟁반을 서로 맞바꾼다. 두 자리 사이에 있는 다른 쟁반은 움직이지 않으며, 쟁반에 적힌 식단 번호도 바뀌지 않는다. 두 자리의 번호가 같으면 해당 쟁반은 그대로 두고 그 작업을 마친다. 작업은 작업표에 적힌 순서대로 하나씩 수행한다. 앞선 작업으로 옮겨진 쟁반이 다음 작업에서 다시 옮겨질 수 있다. 작업표의 번호는 항상 받침대의 자리를 뜻한다. 따라서 어떤 식단 번호가 적힌 쟁반을 찾아서 움직이는 것이 아니라, 지정된 자리에 그 순간 놓여 있는 쟁반을 움직여야 한다. 모든 작업이 끝나면 담당자는 왼쪽 자리부터 차례대로 식단 번호를 읽어 배식 준비가 끝났는지 확인한다. 작업이 하나도 없다면 처음 놓인 순서가 그대로 최종 순서가 된다. 식단 번호가 같은 쟁반끼리 자리를 바꾸는 경우에도 별도의 표시 없이 작업을 수행하면 된다. 처음의 식단 번호 목록과 작업표가 주어질 때, 모든 작업을 끝낸 뒤 각 자리에 놓인 쟁반의 식단 번호를 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 쟁반 수 N과 작업 수 K가 공백으로 구분되어 주어진다. 둘째 줄에 처음 각 자리에 놓인 쟁반의 식단 번호 A₁, A₂, …, Aₙ이 주어진다. 다음 K개의 줄에는 맞바꿀 두 자리의 번호 X와 Y가 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ K ≤ 1,000, 1 ≤ Aᵢ ≤ 1,000, 1 ≤ X, Y ≤ N이다.

출력

모든 작업이 끝난 뒤 1번 자리부터 N번 자리까지의 식단 번호를 한 줄에 공백으로 구분하여 출력한다.

5 3
12 7 9 7 4
1 5
2 4
5 3

4 7 12 7 9

3 0
8 8 2

8 8 2

1 2
15
1 1
1 1

15

출처: Devin.KR 자체 제작