E - 聪明婴儿

得分：500分

问题描述

在AtCoder中有N个婴儿，编号从1到N，以及2×10^5个幼儿园，编号从1到2×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次转移后的平均度量。