← 返回题目列表

AtCoder · abc170_e

E. 聪明的婴儿

中文机器翻译题面 查看原题

分数: 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