配点 : $500$ 点

問題文

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$ 回それぞれの転園後の平等さを求めてください。

制約

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

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

6
2
6

はじめ、幼稚園 $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$ を出力します。

2 2
4208 1234
3056 5678
1 2020
2 2020

3056
4208