using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace debug
{
class main
{
static void Main(string args)
{
//問題クラスを展開
ProgramE a = new ProgramE();
a.main();//実行する
}
}
//ABC170
class ProgramA
{
public void main()
{
//入力
string s = Console.ReadLine().Split(' ');
//入力が0ならその位置を答で出す
for (int i = 0; i < 5; i++)
{
if (s[i] == "0")
Console.WriteLine(i + 1);
}
}
}
class ProgramB
{
public void main()
{
//入力
string s = Console.ReadLine().Split(' ');
int a = int.Parse(s[0]);
int b = int.Parse(s[1]);
//奇数ならあり得ない
if (b % 2 == 1)
{
Console.WriteLine("No");
return;
}
//aの2倍以上4倍以下なら答え
if (a * 2 <= b && b <= 4 * a)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
class ProgramC
{
public void main()
{
//入力
string s = Console.ReadLine().Split(' ');
int x = int.Parse(s[0]);
int n = int.Parse(s[1]);
string a = Console.ReadLine().Split(' ');
int dif = new int[100];
for (int i = 0; i < n; i++)
dif[int.Parse(a[i]) - 1]++;
long ans1 = 0;
long ans2 = 0;
//101まででxとの差が一番小さいものを見つける
for (int i = x - 1; i <= 100; i++)
{
if (i == 100)
{
ans1 = 101;
break;
}
if (dif[i] == 0)
{
ans1 = i + 1;
break;
}
}
//0まででxとの差が一番小さいものを見つける
for (int i = x - 1; i >= -1; i--)
{
if (i == -1)
{
ans2 = 0;
break;
}
if (dif[i] == 0)
{
ans2 = i + 1;
break;
}
}
//もし絶対量が同じなら小さい方、それ以外は絶対値の小さい方を出す
if (ans1 == ans2)
Console.WriteLine(ans1);
Console.WriteLine(ans1);
else
Console.WriteLine(ans2);
}
}
class ProgramD
{
public void main()
{
//入力
long n = long.Parse(Console.ReadLine());
string s = Console.ReadLine().Split(' ');
long a = new long[n];
for (int i = 0; i < n; i++)
a[i] = long.Parse(s[i]);
//n=1のときは例外処理
if (n == 1)
{
Console.WriteLine(1);
return;
}
//ソートする
Array.Sort(a);
//1があれば例外処理
if (a[0] == 1)
{
if (a[0] == a[1])
Console.WriteLine(0);
else
Console.WriteLine(1);
return;
}
//この整数は可能かどうかを見る
long flag = new long[a[n - 1]];
//同じ数があるか探す
for (int i = 0; i < n - 1; i++)
{
if (a[i] == a[i + 1])
{
flag[a[i] - 1] = 2;
}
}
//それぞれの数で残るか検討
for (int i = 0; i < n; i++)
{
//すでに数えたものは無視
if (flag[a[i] - 1] == 1)
continue;
//数えていないものはその倍数の可能性をつぶす
long t = a[i];
t += a[i];
while (t <= a[n - 1])
{
flag[t - 1] = 1;
t += a[i];
}
}
//判定
long ans = 0;
for (int i = 0; i < n; i++)
{
//それぞれのAに対して0のものだけは成立する
if (flag[a[i] - 1] == 0)
ans++;
}
//答え出力
Console.WriteLine(ans);
}
}
class ProgramE
{
//static List<long> list = new List<long>[200001];
static SortedSet<long> list = new SortedSet<long>[200001];
public void main()
{
//入力
string s = Console.ReadLine().Split(' ');
long n = long.Parse(s[0]);
long q = long.Parse(s[1]);
long a = new long[n];//レート
long b = new long[n];//所属幼稚園
for (int i = 0; i < 200001; i++)
list[i] = new SortedSet<long>();
//とりあえず園児に対して所属幼稚園とレートを読む
for (int i = 0; i < n; i++)
{
string t = Console.ReadLine().Split(' ');
a[i] = long.Parse(t[0]);
b[i] = long.Parse(t[1]);
list[b[i]].Add((a[i] << 32) + i);//幼稚園児ごとにIDで分けておかないと全部消える
}
//答候補入れる
for (int i = 1; i < 200001; i++)
{
if (list[i].Count != 0)
list[0].Add(list[i].Max);
}
//転園していく
for(int i = 0;i < q;i++)
{
string x = Console.ReadLine().Split();
long c = long.Parse(x[0]);
long d = long.Parse(x[1]);
//移動前の最大値を削除
list[0].Remove(list[b[c - 1]].Max);
//移動後の幼稚園も削除
if(list[d].Count != 0)
list[0].Remove(list[d].Max);
//移動する前のその位置を削除する
}
}
}
}
//移動後の幼稚園に追加する
list[d].Add((a[c -1] << 32) + c -1);
//移動後の幼稚園の最大値も追加
list[0].Add(list[d].Max);
//移動する前の最大値を追加
if(list[b[c - 1]].Count != 0)
list[0].Add(list[b[c - 1]].Max);
//園児の所属を更新
b[c - 1] = d;
//最小値を出力
Console.WriteLine((list[0].Min >> 32
