옷걸이 자리 교환 기록

문제

한 세탁소에는 손님에게 돌려줄 옷을 걸어 두는 일자형 보관대가 있다. 보관대의 자리는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 자리에는 옷걸이가 정확히 하나씩 걸려 있고, 각 옷걸이에는 서로 다른 정수 표찰이 달려 있다. 표찰 번호는 1부터 N까지이며, 모든 번호가 정확히 한 번씩 나타난다. 자리 번호는 보관대에 붙어 있으므로 옷걸이를 옮겨도 바뀌지 않는다. 직원은 작업 공간을 정리하면서 두 자리의 옷걸이를 맞바꾸는 작업을 여러 번 수행했다. 한 번의 작업에는 두 자리 번호 x와 y가 기록된다. 이 작업은 현재 x번 자리에 걸린 옷걸이와 현재 y번 자리에 걸린 옷걸이를 서로 바꾸는 것을 뜻한다. 표찰만 떼어 옮기는 것이 아니라 표찰이 달린 옷걸이 전체를 옮긴다. 나머지 자리의 옷걸이는 움직이지 않는다. 교환 기록은 실제 작업이 이루어진 순서대로 주어진다. 따라서 앞선 교환으로 바뀐 배치를 다음 교환에서 그대로 사용해야 한다. 같은 자리 번호가 여러 기록에 등장할 수 있으며, x와 y가 같을 수도 있다. 두 번호가 같으면 같은 자리의 옷걸이를 지정한 것이므로 그 작업 뒤에도 전체 배치는 변하지 않는다. 처음 배치와 Q번의 교환 기록을 보고 모든 작업이 끝난 뒤의 표찰 번호를 알아내려고 한다. N은 1 이상 1,000 이하의 정수이고, Q는 0 이상 1,000 이하의 정수다. 교환 기록이 하나도 없다면 처음 배치를 그대로 출력한다. 최종 결과는 옷걸이를 표찰 번호순으로 정렬한 결과가 아니라, 보관대의 1번 자리부터 N번 자리까지 실제로 걸려 있는 순서다. 각 자리에 남은 표찰 번호를 차례대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N과 Q가 주어진다. 1 ≤ N ≤ 1,000, 0 ≤ Q ≤ 1,000이다.
둘째 줄에 처음 각 자리에 걸린 표찰 번호 N개가 주어진다. 이 수들은 1부터 N까지의 순열이다.
다음 Q개 줄에는 교환할 자리 번호 x와 y가 주어진다. x와 y는 각각 1 이상 N 이하의 정수다.

출력

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

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

2 3 5 1 4

3 0
2 3 1

2 3 1

1 2
1
1 1
1 1

1

출처: Devin.KR 자체 제작