当前没有测试数据。

题目描述

经过发展，T城的特工队伍壮大了！一些特工发展了新的下线。为了组织的保密，新的特工加入以后，依然需要保持单线联系。请输出新的单线联系序列。

输入格式

第一行两个整数 $n,m$，代表原有 $n$ 个特工，有 $m$ 名新特工 第二行 $n$ 个整数，依次代表每一位特工的代号。其中第 $i$ 个特工，是第 $i+1$ 个特工的上级。第 1 个特工没有上级。 接下来 $m$ 行，每行两个整数 $p,q$，代表代号为 $p$ 的特工，发展了代号为 $q$ 的特工的下线。

输出格式

一行 $n+m$ 个整数，代表新的联系序列

5 1
1 3 2 5 4
2 6

1 3 2 6 5 4

提示

代号为 2 的特工，发展了新的下线 6 。原来 2 的下线 5，成为 6 的下线。 $n \le 10000，m \le 100$