C-旋转跳跃_牛客编程巅峰赛S1第3场

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题意

有一个长为 $n$ 的排列 $p$ ，与 $m$ 对 $(x_i, y_i)$ 。

每对 $(x_i, y_i)$ 表示可以将 $p_{x_i}$ 的值与 $p_{y_i}$ 的值互换。

$m$ 对 $(x_i, y_i)$ 的使用顺序与次数不限。

求任意次操作之后他能得到的字典序最小的排列是什么

字典序定义：对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。(来自百度百科)

输入

第一个参数为 $n$ ， $1\leq n \leq 100,000$

第二个参数为 $m$ ， $1\leq m \leq 100,000$

第三个参数为初始排列 $p$ ， $1\leq p_i\leq n$

第四个参数为 $m$ 对 $(x_i, y_i)$ ， $1\leq x_i, y_i\leq n, x_i \neq y_i$

字典序最小的排列

示例1

输入

复制

5,3,[5,2,3,4,1],[(2,4),(1,4),(3,4)]

返回值

复制

[2,3,4,5,1]

说明

1. 交换 (3, 4), 交换后的序列为： 5, 2, 4, 3, 1
2. 交换 (2, 4), 交换后的序列为： 5, 3, 4, 2, 1
3. 交换 (1, 4), 交换后的序列为： 2, 3, 4, 5, 1