题目描述

我有 n 件物品，第 i 件物品的价格为 ai​。

你可以进行 q 种操作，第 i 种操作是将第 xi​ 件物品和第 yi​ 件物品的价格交换。

每种操作可以进行无限次。

但是跟我换东西，需要保证经过所有交换后的 ‘a‘ 序列是我最喜欢的，即不会存在别的交换后的序列 ‘‘a‘‘ 满足 ‘a‘‘ 的字典序大于 ‘a‘。

输入格式

第 1 行，两个正整数 n 和 q。

第 2 行，共 n 个正整数，第 i 个数表示 ai​。

第 3∼q+2 行，每行两个正整数xi​,yi​。

输出格式

一行，共 n 个正整数表示答案。

输入输出样例

输入数据 1

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

输出数据 1

5 4 3 2 1
```## 输入数据 2

```input2
10 3
1 5 4 3 2 4 2 8 4 6
1 3
3 4
2 3

输出数据 2

5 4 3 1 2 4 2 8 4 6

提示

数据规模与约定

对于 100% 的数据， 保证 ai​≤10^6。