题目描述

小珅和小泽面前摆放着 N 个盒子。开始时，每个盒子里恰好有一个小球，第 i 个盒子中小球的颜色编号为 C_i。

接下来，他们要进行 Q 次操作。每次操作给出两个不同的盒子编号 a 和 b：小珅会把第 a 个盒子中的所有小球全部倒入第 b 个盒子中，此后第 a 个盒子变为空盒；小泽则需要立即统计第 b 个盒子中共有多少种不同颜色的小球。

请你帮助小泽，在每次操作后输出相应的统计结果。若第 b 个盒子为空，则不同颜色的数量为 0。

输入格式

第一行包含两个整数 N 和 Q，分别表示盒子的数量和操作次数。

第二行包含 N 个整数 C_1,C_2,...,C_N，其中 C_i 表示第 i 个盒子中初始小球的颜色编号。

接下来 Q 行，每行包含两个整数 a 和 b，表示把第 a 个盒子中的所有小球移入第 b 个盒子。保证 a 不等于 b。

输出格式

输出 Q 行。每次操作后输出一行一个整数，表示此时第 b 个盒子中不同颜色的小球数量。

样例输入

6 5
1 1 1 2 2 3
1 2
6 4
5 1
3 6
4 6

样例输出

1
2
1
1
3

数据范围

• 2 <= N <= 200000；
• 1 <= Q <= 200000；
• 1 <= C_i <= N；
• 1 <= a,b <= N，且 a 不等于 b。

2 1
1 2
1 2

2

2 3
1 1
1 2
2 1
1 2

1
1
1