카페 진열대의 자리 교환

문제

한 카페에서는 손님에게 보여 줄 음료 모형을 긴 진열대에 놓는다. 진열대에는 N개의 자리가 있으며, 왼쪽부터 차례로 1번부터 N번까지 번호가 붙어 있다. 각 자리에는 음료 모형이 정확히 하나씩 놓여 있다. 모형에는 음료의 종류를 나타내는 양의 정수 번호가 적혀 있으며, 같은 종류의 모형이 여러 자리에 놓여 있을 수도 있다. 카페 직원은 새로운 진열 모습을 시험하기 위해 두 자리의 모형을 서로 바꾸는 작업을 한다. 한 번의 작업에서는 자리 번호 두 개를 고른다. 고른 두 자리에 현재 놓여 있는 모형을 동시에 맞바꾸며, 다른 자리의 모형은 그대로 둔다. 모형을 새로 추가하거나 진열대에서 없애는 작업은 하지 않는다. 직원이 적어 둔 작업은 모두 M개이고, 적힌 순서대로 수행한다. 따라서 어떤 작업에서 옮긴 모형은 뒤의 작업에서 다시 옮겨질 수 있다. 각 작업에 적힌 번호는 음료의 종류 번호가 아니라 진열대의 자리 번호다. 같은 종류의 모형이 여러 개 있더라도, 해당 작업에서 지정한 두 자리만 확인하면 된다. 두 자리 번호가 같을 수도 있다. 이 경우에는 한 자리의 모형을 자기 자신과 바꾸는 것이므로 진열 상태가 달라지지 않는다. 서로 다른 두 자리에 같은 종류의 모형이 놓여 있는 경우에도 작업 전후에 보이는 종류 번호의 배열은 같다. 이러한 작업 역시 다른 작업과 마찬가지로 순서에 따라 처리한다. 모든 작업을 마친 뒤 직원은 진열대의 최종 상태를 기록하려 한다. 기록할 때는 모형이 이동한 경로나 처음 놓였던 위치를 적지 않고, 현재 각 자리에 놓인 모형의 종류 번호만 왼쪽부터 차례대로 적는다. 작업이 하나도 없다면 처음 진열한 상태를 그대로 기록한다. 처음의 종류 번호들과 자리 교환 작업들이 주어질 때, 직원이 기록할 최종 종류 번호의 순서를 구한다.

입력

첫째 줄에 자리 수 N과 작업 수 M이 공백으로 구분되어 주어진다. 둘째 줄에 처음 각 자리에 놓인 모형의 종류 번호 C_1부터 C_N까지가 공백으로 구분되어 주어진다. 다음 M개 줄에는 작업 순서대로 두 자리 번호 X와 Y가 공백으로 구분되어 주어진다. 모든 입력은 정수이며, 1 ≤ N ≤ 1,000, 0 ≤ M ≤ 1,000, 1 ≤ C_i ≤ 1,000, 1 ≤ X, Y ≤ N이다. 종류 번호는 중복될 수 있고 X와 Y는 같을 수 있다.

출력

모든 작업이 끝난 뒤 1번 자리부터 N번 자리까지 놓인 모형의 종류 번호 N개를 공백 하나로 구분하여 한 줄에 출력한다.

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

2 9 4 7 4

3 0
8 8 1

8 8 1

4 3
6 3 6 2
1 3
2 2
3 4

6 3 2 6

출처: Devin.KR 자체 제작