彩球

题目描述

有编号为 $1, 2, \ldots, N$ 的 $N$ 个箱子,初始时箱子 $i$ 中装有 $1$ 个颜色为 $C_i$ 的球。

给定 $Q$ 个查询,请按顺序处理它们。

每个查询由整数对 $(a, b)$ 给出,内容如下:

• 将箱子 $a$ 中的所有球移到箱子 $b$,然后输出箱子 $b$ 中有多少种不同颜色的球。

注意,箱子 $a$ 和箱子 $b$ 可能为空。

输入格式

输入按以下格式从标准输入给出。这里,$\text{query}_i$ 表示第 $i$ 个查询。

$N$ $Q$
$C_1$ $C_2$ $\ldots$ $C_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询以如下格式给出:

$a$ $b$

输出格式

输出 $Q$ 行。

第 $i$ 行输出对第 $i$ 个查询的答案。

样例

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

1
2
1
1
3

• 在第 $1$ 个查询中,将箱子 $1$ 的所有球移到箱子 $2$。箱子 $2$ 中现在装有 $2$ 个颜色为 $1$ 的球,因此输出 $1$。
• 在第 $2$ 个查询中,将箱子 $6$ 的所有球移到箱子 $4$。箱子 $4$ 中现在装有 $1$ 个颜色为 $2$ 的球和 $1$ 个颜色为 $3$ 的球,因此输出 $2$。
• 在第 $3$ 个查询中,将箱子 $5$ 的所有球移到箱子 $1$。箱子 $1$ 中现在装有 $1$ 个颜色为 $2$ 的球,因此输出 $1$。
• 在第 $4$ 个查询中,将箱子 $3$ 的所有球移到箱子 $6$。箱子 $6$ 中现在装有 $1$ 个颜色为 $1$ 的球,因此输出 $1$。
• 在第 $5$ 个查询中,将箱子 $4$ 的所有球移到箱子 $6$。箱子 $6$ 中现在装有 $1$ 个颜色为 $1$ 的球、$1$ 个颜色为 $2$ 的球和 $1$ 个颜色为 $3$ 的球,因此输出 $3$。

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

1
2
0

数据范围

• $1 \le N, Q \le 200000$
• $1 \le C_i \le N$
• $1 \le a, b \le N$
• $a \neq b$
• 输入的所有值均为整数