排列

题号：NC223142
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛有 $M$ 个 $1 \sim N$ 的排列 $p_0,p_1,...,p_{M-1}$ ，因为写下所有的排列太费时间，而且也会写下很多数字，牛牛觉得这过程没有什么意义，经过观察后牛牛发现对于 $i=1,2,3,...,M-1$ ， $p_i$ 是 $p_{i-1}$ 交换第 $x_i$ 和 $y_i$ 个数字得到的，所以牛牛就先在第一行写下了第一个排列，然后接下来写的全是 $x_i$ 和 $y_i$ ，由此完美的解决了排列的存储问题。

但是这样又一个问题诞生了，若牛牛写下所有的数字，他可以轻松的按字典序比较任意两个排列的大小，但现在这种存储方式，却是让这个问题变得十分的复杂，所以现在你的任务就是：将这个 $M$ 个排列按照字典序从小到大排(若有一样的排列，则让下标较小的出现在前面)得到 $p_{a_1} \le p_{a_2} \le ... \le p_{a_m}$ ，然后输出 $a_1,a_2,...,a_m$ 。

输入描述:

第一行给出两个正整数 $N,M$ ，含义如题

第二行给出 $N$ 个正整数表示 $p_0$

接下来 $M-1$ 行每行两个正整数，其中第 $i$ 行两个正整数表示 $x_i,y_i$

$2 \le N \le 10^5$

$1 \le M \le 10^5$

$p_0$ 是一个 $1 \sim N$ 的排列

$1 \le x_i,y_i \le N, x_i \neq y_i$

输出描述:

在一行中输出  个以空格分隔的整数

示例1

输入

复制

输出

复制

1 3 2 0

说明

，将  的第一个数字 () 和第二个数字 () 交换，得到 ，类似可以得到 。按字典序排序得到