E - Smart Infants 解説 /

実行時間制限: 3.5 sec / メモリ制限: 1024 MB

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

入力例 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 には幼児 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 2
4208 1234
3056 5678
1 2020
2 2020

出力例 2

3056
4208

Score : 500 points

Problem Statement

There are N infants registered in AtCoder, numbered 1 to N, and 2\times 10^5 kindergartens, numbered 1 to 2\times 10^5. Infant i has a rating of A_i and initially belongs to Kindergarten B_i.

From now on, Q transfers will happen. After the j-th transfer, Infant C_j will belong to Kindergarten D_j.

Here, we define the evenness as follows. For each kindergarten with one or more infants registered in AtCoder, let us find the highest rating of an infant in the kindergarten. The evenness is then defined as the lowest among those ratings.

For each of the Q transfers, find the evenness just after the transfer.

Constraints

  • 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
  • All values in input are integers.
  • In the j-th transfer, Infant C_j changes the kindergarten it belongs to.

Input

Input is given from Standard Input in the following format:

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

Output

Print Q lines. The j-th line should contain the evenness just after the j-th transfer.

Sample Input 1

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

Sample Output 1

6
2
6

Initially, Infant 1, 4 belongs to Kindergarten 1, Infant 2, 5 belongs to Kindergarten 2, and Infant 3, 6 belongs to Kindergarten 3.

After the 1-st transfer that makes Infant 4 belong to Kindergarten 3, Infant 1 belongs to Kindergarten 1, Infant 2, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 6, 9, respectively. The lowest among them is 6, so the 1-st line in the output should contain 6.

After the 2-nd transfer that makes Infant 2 belong to Kindergarten 1, Infant 1, 2 belong to Kindergarten 1, Infant 5 belongs to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 2, 9, respectively. The lowest among them is 2, so the 2-nd line in the output should contain 2.

After the 3-rd transfer that makes Infant 1 belong to Kindergarten 2, Infant 2 belongs to Kindergarten 1, Infant 1, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 6, 8, 9, respectively. The lowest among them is 6, so the 3-rd line in the output should contain 6.

Sample Input 2

2 2
4208 1234
3056 5678
1 2020
2 2020

Sample Output 2

3056
4208