You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

E. 转学生

题目描述

有 $N$ 个学生，编号为 $1 \sim N$，另有 $2 \times 10^5$ 个学校，编号为 $1 \sim 2 \times 10^5$。

编号为 $i$ 的学生的 Rating 为 $A_i$，最初位于 $B_i$ 号学校。

进行 $Q$ 次操作，第 $j$ 次操作后 $C_j$ 号学生会转到 $D_j$ 号学校。

定义“均衡值”为：找出每个学校中 Rating 最高的学生，他们中最低的 Rating 为“均衡值”。

输出每次操作之后的“均衡值”。

输入格式

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$ 行答案，每行代表一次操作后的均衡值。

样例

输入样例 #1

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

输出样例 #1

6
2
6

输入样例 #2

2 2
4208 1234
3056 5678
1 2020
2 2020

输出样例 #2

3056
4208

数据范围与提示

• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le C_j \le N$
• $1 \le B_i, D_j \le 2 \times 10^5$