Description

给定 $N$ 个编号为 $1$ 到 $N$ 的饭盒。初始时，饭盒 $i$ 中包含一个馅为 $C_i$ 的小笼包。

现在需要处理 $Q$ 个查询，每个查询由两个整数 $(a, b)$ 组成，要求执行以下操作：

1. 将饭盒 $a$ 中的所有小笼包移动到饭盒 $b$
2. 输出移动后饭盒 $b$ 中不同馅小笼包的数量

注意：

• 查询需要按顺序处理
• 饭盒 $a$ 和 $b$ 在操作前可能是空的
• 保证 $a \neq b$

Format

Input

第一行包含两个整数 $N$ 和 $Q$， $1 \leq N, Q \leq 2 \times 10^5$ 第二行包含 $N$ 个整数 $C_1, C_2, ..., C_N$，$1 \leq C_i \leq N$ 接下来 $Q$ 行，每行包含两个整数 $a$ 和 $b$，表示一个查询，$1 \leq a, b \leq N$，$a \neq b$

Output

对于每个查询，输出一行，表示操作后饭盒 $b$ 中不同馅小笼包的数量

Samples

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

1
2
1
1
3

1. 第一次查询后，饭盒2中有两个馅1的小笼包，不同馅数为1
2. 第二次查询后，饭盒4中有馅2和3的小笼包，不同馅数为2
3. 第三次查询后，饭盒1中有馅2的小笼包，不同馅数为1
4. 第四次查询后，饭盒6中有馅1的小笼包，不同馅数为1
5. 第五次查询后，饭盒6中有馅1、2、3的小笼包，不同馅数为3