E-卡片赠送_2024寒假训练赛2

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

题目描述

某公司正在举行年会，老板提议玩一个游戏。
年会上有 $n$ 个员工，每个员工初始拥有一张卡片，卡片上的数值为 $a_i$ 。
老板宣布，谁最终拥有的不同数值的卡片的数量最多，谁就能获得价值三倍年终奖的奖励。
因此，员工们开始了 $q$ 次暗中交易。
每次交易只涉及两个人，分别用 $x$ 和 $y$ 来表示， $y$ 给了 $x$ 一些好处，使得 $x$ 把自己所有的卡片交给 $y$ 。
对于每一次交易，请输出交易完毕后，当前的获奖员工的编号。
如果有多个员工的不同卡片数量相同，输出员工编号最小的那个。

输入描述:

第一行有两个整数  和  。
第二行有  个整数  。
随后  行，每行两个整数  。

输出描述:

输出  行，每行一个整数，代表当前的获奖者的编号。
如果有多个员工的不同卡片数量相同，输出员工编号最小的那个。

示例1

输入

复制

5 5
11 45 14 1919 810
1 2
3 5
4 5
2 3
5 3

输出

复制

说明

第一次交易后， 号员工有两张不同数值的卡片。
第二次交易后， 号员工也有两张不同数值的卡片，但编号比  号员工大。
第三次交易后， 号员工有三张不同数值的卡片。
第四次交易后， 号员工有两张不同数值的卡片。
第五次交易后， 号员工有五张不同数值的卡片。