多重映射
题号：NC266929
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,在书写代码时，我们时常会使用到批量查找替换的功能。现在，我们需要对一些数字进行类似的操作。
\,\,\,\,\,\,\,\,\,\,（本题没有题图，因为说话的人在映射后丢失了！）
\,\,\,\,\,\,\,\,\,\,
\,\,\,\,\,\,\,\,\,\,已知一个由数字构成的序列 A ，不妨定义一个函数 M(x)=y 表示将序列 A 中全部的数字 x 都替换为 y 。例如 A=\{2,2,4,5,1,4\} ，执行一次 M(2)=1 操作后，序列变为 A'=\{1,1,4,5,1,4\} ，很神奇吧！
\,\,\,\,\,\,\,\,\,\,这样的替换显然是能够进行反复叠加的，举例说明，对于上方操作过后的 A' 再执行一次 M(1)=2 操作，序列会变为 A''=\{2,2,4,5,2,4\} 。
\,\,\,\,\,\,\,\,\,\,现在，给出若干个这样的操作，请你输出修改过后的序列。

输入描述:

\,\,\,\,\,\,\,\,\,\,每个测试文件均包含多个测试点。第一行输入一个整数 T (1\leq T\leq 10^5) 代表测试数据组数，每组测试数据描述如下：
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n 和 m (1\leq n, m\leq 10^5) 表示序列长度和操作数量。
\,\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n (1\leq a_i \leq 10^6) 表示给定的序列。
\,\,\,\,\,\,\,\,\,\,此后 m 行，第 i 行输入两个整数 x_i 和 y_i (1\leq x_i, y_i\leq 10^6) 表示一个操作。
\,\,\,\,\,\,\,\,\,\,保证所有测试用例的 n 之和不会超过 2 \cdot 10^5 ，m 之和不会超过 2 \cdot 10^5 。

输出描述:

\,\,\,\,\,\,\,\,\,\,对于每组数据，你都需要在一行上输出 n 个整数，代表执行操作后的序列，数字彼此间通过单个空格间隔。
示例1

输入

复制 
2
6 1
2 2 4 5 1 4
2 1
6 2
2 2 4 5 1 4
2 1
1 6

输出

复制 
1 1 4 5 1 4
6 6 4 5 6 4

说明

\,\,\,\,\,\,\,\,\,\,该样例已经在题干中加以解释。
示例2

输入

复制 
1
3 5
20 17 18
8 16
15 1
20 2
20 1
15 1

输出

复制 
2 17 18

备注: