分数: 500 点
问题陈述
有 N 在 AtCoder 中注册的婴儿,编号 1 to N,和 2\times 10^5 幼儿园,编号 1 to 2\times 10^5。 婴儿 i 的评级为 A_i 最初属于幼儿园 B_i.
从现在开始, Q 将会发生转移。 之后 j第次转移,婴儿 C_j 将属于幼儿园 D_j.
在这里,我们定义 均匀度 如下。对于在 AtCoder 中注册了一名或多名婴儿的每个幼儿园,让我们找到该幼儿园中一名婴儿的最高评分。然后将均匀度定义为这些评级中最低的。
对于每个 Q 转移,检查转移后的均匀度。
约束
- 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 更改其所属幼儿园。
输入
输入由标准输入按以下格式给出:
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第次传输。
示例输入 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
最初,婴儿 1, 4 属于幼儿园 1,婴儿 2, 5 属于幼儿园 2和婴儿 3, 6 属于幼儿园 3.
之后 1-st 转移使婴儿 4 属于幼儿园 3,婴儿 1 属于幼儿园 1,婴儿 2, 5 属于幼儿园 2和婴儿 3, 4, 6 属于幼儿园 3。幼儿园婴儿最高评分 分别是 1, 2, 3 是 8, 6, 9。其中最低的是 6,所以 1- 输出中的第行应包含 6.
之后 2-nd 转移使婴儿 2 属于幼儿园 1,婴儿 1, 2 属于幼儿园 1,婴儿 5 属于幼儿园 2和婴儿 3, 4, 6 属于幼儿园 3。幼儿园婴儿最高评分 分别是 1, 2, 3 是 8, 2, 9。其中最低的是 2,所以 2- 输出中的第行应包含 2.
之后 3-rd 传输使婴儿 1 属于幼儿园 2,婴儿 2 属于幼儿园 1,婴儿 1, 5 属于幼儿园 2和婴儿 3, 4, 6 属于幼儿园 3。幼儿园婴儿最高评分 分别是 1, 2, 3 是 6, 8, 9。其中最低的是 6,所以 3-rd 输出中的行应包含 6.
示例输入 2
2 2 4208 1234 3056 5678 1 2020 2 2020
示例输出 2
3056 4208