智慧幼儿

题目描述

有 $N$ 名参加 AtCoder 的幼儿,编号为 $1$ 到 $N$。此外,有 $2\times 10^5$ 所幼儿园,编号为 $1$ 到 $2\times 10^5$。 幼儿 $i$ 的等级为 $A_i$,最初隶属于幼儿园 $B_i$。

接下来将进行 $Q$ 次转园。 在第 $j$ 次转园中,将幼儿 $C_j$ 的所属变更为幼儿园 $D_j$。

这里,「平等度」定义为:对于每一所有至少一名幼儿的幼儿园,求出该幼儿园内等级最高的幼儿的等级,再取这些值中的最小值。

请计算每次转园后的平等度。

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_N$ $B_N$
$C_1$ $D_1$
$C_2$ $D_2$
$:$
$C_Q$ $D_Q$

输出格式

输出 $Q$ 行。 第 $j$ 行输出第 $j$ 次转园后的平等度。

样例

6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

6
2
6

最初,幼儿园 $1$ 有幼儿 $1, 4$,幼儿园 $2$ 有幼儿 $2, 5$,幼儿园 $3$ 有幼儿 $3, 6$。

第 $1$ 次转园把幼儿 $4$ 转到幼儿园 $3$ 后,幼儿园 $1$ 有幼儿 $1$,幼儿园 $2$ 有幼儿 $2, 5$,幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 中等级最高的幼儿的等级为 $8$,幼儿园 $2$ 中为 $6$,幼儿园 $3$ 中为 $9$。这些值的最小值为 $6$,因此第 $1$ 行输出 $6$。

第 $2$ 次转园把幼儿 $2$ 转到幼儿园 $1$ 后,幼儿园 $1$ 有幼儿 $1, 2$,幼儿园 $2$ 有幼儿 $5$,幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 中等级最高的幼儿的等级为 $8$,幼儿园 $2$ 中为 $2$,幼儿园 $3$ 中为 $9$。这些值的最小值为 $2$,因此第 $2$ 行输出 $2$。

第 $3$ 次转园把幼儿 $1$ 转到幼儿园 $2$ 后,幼儿园 $1$ 有幼儿 $2$,幼儿园 $2$ 有幼儿 $1, 5$,幼儿园 $3$ 有幼儿 $3, 4, 6$。幼儿园 $1$ 中等级最高的幼儿的等级为 $6$,幼儿园 $2$ 中为 $8$,幼儿园 $3$ 中为 $9$。这些值的最小值为 $6$,因此第 $3$ 行输出 $6$。

2 2
4208 1234
3056 5678
1 2020
2 2020

3056
4208

数据范围

• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq C_j \leq N$
• $1 \leq B_i,D_j \leq 2 \times 10^5$
• 输入均为整数。
• 第 $j$ 次转园前后,幼儿 $C_j$ 的所属不同。