题目描述

AtCoder に参加している幼児が $N$ 人おり、$1$ から $N$ の番号が付けられています。また、幼稚園が $2\times\ 10^5$ 校あり、$1$ から $2\times\ 10^5$ の番号が付けられています。 幼児 $i$ のレートは $A_i$ であり、はじめ幼稚園 $B_i$ に所属しています。

これから $Q$ 回にわたって、転園が行われます。 $j$ 回目の転園では、幼児 $C_j$ の所属を幼稚園 $D_j$ に変更します。

ここで、「平等さ」を、AtCoderに参加している幼児が一人以上いるような幼稚園それぞれについて園内で最もレートの高い幼児のレートを求め、その最小値として得られる値とします。

$Q$ 回それぞれの転園後の平等さを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 回目の転園の後の平等さを出力せよ。

题目大意

有 $N$ 婴儿注册了 AtCoder，编号为 $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 为“均衡值”。

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

6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

6
2
6

2 2
4208 1234
3056 5678
1 2020
2 2020

3056
4208

提示

制約

• $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$ の所属は異なる。

Sample Explanation 1

はじめ、幼稚園 $1$ には幼児 $1,\ 4$、幼稚園 $2$ には幼児 $2,\ 5$、幼稚園 $3$ には幼児 $3,\ 6$ が所属しています。 $1$ 回目の転園で幼児 $4$ の所属を幼稚園 $3$ に変更すると、幼稚園 $1$ には幼児 $1$、幼稚園 $2$ には幼児 $2,\ 5$、幼稚園 $3$ には幼児 $3,\ 4,\ 6$ が所属している状態になります。幼稚園 $1$ で最もレートの高い幼児のレートは $8$、幼稚園 $2$ では $6$、幼稚園 $3$ では $9$ です。これらの最小値は $6$ であるので、$1$ 行目には $6$ を出力します。 $2$ 回目の転園で $2$ 番目の幼児の所属を幼稚園 $1$ に変更すると、幼稚園 $1$ には幼児 $1,\ 2$、幼稚園 $2$ には幼児 $5$、幼稚園 $3$ には幼児 $3,\ 4,\ 6$ が所属している状態になります。幼稚園 $1$ で最もレートの高い幼児のレートは $8$、幼稚園 $2$ では $2$、幼稚園 $3$ では $9$ です。これらの最小値は $2$ であるので、$2$ 行目には $2$ を出力します。 $3$ 回目の転園で $1$ 番目の幼児の所属を幼稚園 $2$ に変更すると、幼稚園 $1$ には幼児 $2$、幼稚園 $2$ には幼児 $1,\ 5$、幼稚園 $3$ には幼児 $3,\ 4,\ 6$ が所属している状態になります。幼稚園 $1$ で最もレートの高い幼児のレートは $6$、幼稚園 $2$ では $8$、幼稚園 $3$ では $9$ です。これらの最小値は $6$ であるので、$3$ 行目には $6$ を出力します。