6795: 幼儿园老大
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：48
解决：7
题目描述
付哥是幼儿园的老大，他手下有$N$个小朋友，并且有$2*10^5$个从$1$编号到$2*10^5$的班级，最初每个小朋友有一个可爱程度$a_i$并且属于$b_i$班。
从现在开始会按顺序发生$Q$次转班的行为，第$c_j$个小朋友将转到$d_j$班去。
付哥为什么是幼儿园老大呢？因为他是管理小朋友转班的。他可以很快的算出在第$j$次转班后的可爱均匀程度。
对于每个有一个或多个小朋友的班级，找出该班级中小朋友的最高可爱程度，可爱均匀程度就是这些最高可爱程度中的最低值。
从现在开始会按顺序发生$Q$次转班的行为，第$c_j$个小朋友将转到$d_j$班去。
付哥为什么是幼儿园老大呢？因为他是管理小朋友转班的。他可以很快的算出在第$j$次转班后的可爱均匀程度。
对于每个有一个或多个小朋友的班级，找出该班级中小朋友的最高可爱程度，可爱均匀程度就是这些最高可爱程度中的最低值。
输入
$N$ $Q$ $(1 \leq\ N,Q \leq\ 2*10^5)$
$a_1$ $b_1$
$a_2$ $b_2$
$...$
$a_N$ $b_N$
$c_1$ $d_1$
$c_2$ $d_2$
$...$
$c_Q$ $d_Q$
$(1 \leq\ a_i \leq\ 10^9)$
$(1 \leq\ c_i \leq\ N)$
$(1 \leq\ b_i,d_i \leq\ 2*10^5)$
$a_1$ $b_1$
$a_2$ $b_2$
$...$
$a_N$ $b_N$
$c_1$ $d_1$
$c_2$ $d_2$
$...$
$c_Q$ $d_Q$
$(1 \leq\ a_i \leq\ 10^9)$
$(1 \leq\ c_i \leq\ N)$
$(1 \leq\ b_i,d_i \leq\ 2*10^5)$
输出
每次完成转班后输出可爱均匀程度。
样例输入 复制
6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2
样例输出 复制
6
2
6