题目描述

有 $N$ 婴儿注册了 $gdfzoj$ ，编号为 $1\sim N$，另有 $2\times10^5$ 个幼儿园，编号为 $1\sim 2\times10^5$。编号为 $i$ 的婴儿 Rating 为 $A_i$，最初位于 $B_i$ 号幼儿园。

进行 $Q$ 次操作，第 $j$ 次操作后 $C_j$ 号婴儿会转到 $D_j$ 号幼儿园。

定义“均衡值”为：找出每个幼儿园中 Rating 最高的婴儿，他们中最低的 Rating 为“均衡值”。

对于每次操作，求出操作后的“均衡值”。

输入格式

第一行输入两个整数 $N,Q$ 。

接下来 $N$ 行，每行输入两个整数 $A_i,B_i$ 。

接下来 $Q$ 行，每行输入两个整数 $C_i,D_i$ 。

输出格式

输出 $Q$ 行，每行输出该次操作之后的均衡值。

样例 #1

样例输入 #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$ 。

第一次操作，让 $4$ 号转去了幼儿园 $3$ ，此时幼儿园 $1$ 的最高 rating 是 $1$ 号的 $8$ 分 ，幼儿园 $2$ 的最高 rating 是 $1$ 号的 $6$ 分 ，幼儿园 $3$ 的最高 rating 是 $1$ 号的 $9$ 分。

在这三个里面最小是 $6$ 分，所以均衡值是 $6$ 。

后面两次操作以此类推。

样例 #2

样例输入 #2

2 2
4208 1234
3056 5678
1 2020
2 2020

样例输出 #2

3056
4208

提示

对于 $100\%$ 的数据：

• $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$
• 保证操作不会出现自己转到自己的情况