#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
const int INF=1e9;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define X F
#define Y S
struct node
{
int mn,cnt,tag;
node(): mn(INF),cnt(1),tag(0){}
node operator+(const node &a)
{
node rt;
if(a.mn<mn) rt.mn=a.mn,rt.cnt=a.cnt;
else if(a.mn>mn) rt.mn=mn,rt.cnt=cnt;
else rt.mn=mn,rt.cnt=a.cnt+cnt;
rt.tag=0;
return rt;
}
}st[N<<2];
vector<vector<int> > p;
pair<int,int> seat[N];
int dx[4]={0,0,-1,-1},dy[4]={0,-1,0,-1};
int sz;
void give_tag(int t,int id)
{
st[id].tag+=t;
if(st[id].mn==INF) st[id].mn=t;
else st[id].mn+=t;
}
void tag_down(int id)
{
give_tag(st[id].tag,id<<1);
give_tag(st[id].tag,id<<1|1);
st[id].tag=0;
}
void build(int l,int r,int id)
{
if(l==r) st[id]=node();
else
{
int mid=l+r>>1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
st[id]=st[id<<1]+st[id<<1|1];
}
}
void modify(int l,int r,int ql,int qr,int t,int id)
{
if(ql<=l&&r<=qr)
{
give_tag(t,id);
return;
}
if(l!=r) tag_down(id);
int mid=l+r>>1;
if(ql<=mid) modify(l,mid,ql,qr,t,id<<1);
if(qr>mid) modify(mid+1,r,ql,qr,t,id<<1|1);
st[id]=st[id<<1]+st[id<<1|1];
}
void calc(int x,int y,int t)
{
//cout<<"begin calc("<<x<<" "<<y<<" "<<t<<")\n";
int tmp[4]={p[x][y],p[x+1][y],p[x][y+1],p[x+1][y+1]};
sort(tmp,tmp+4);
if(tmp[0]!=tmp[1])
{
//cout<<"modifying tmp[0] tmp[1]-1: "<<tmp[0]<<" "<<tmp[1]-1<<"\n";
modify(1,sz,tmp[0],tmp[1]-1,t,1);
//cout<<"modify tmp[0] tmp[1]-1 done: "<<tmp[0]<<" "<<tmp[1]-1<<"\n";
}
if(tmp[2]!=tmp[3])
{
//cout<<"modifying tmp[2] tmp[3]-1: "<<tmp[2]<<" "<<tmp[3]-1<<"\n";
modify(1,sz,tmp[2],tmp[3]-1,t,1);
//cout<<"modify tmp[2] tmp[3]-1 done: "<<tmp[2]<<" "<<tmp[3]-1<<"\n";
}
//cout<<"end calc("<<x<<" "<<y<<" "<<t<<")\n";
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
sz=H*W;
p.resize(H+2,vector<int>(W+2,sz+1));
rep(i,sz)
{
p[R[i]+1][C[i]+1]=i+1;
seat[i+1]={R[i]+1,C[i]+1};
}
//cout<<"p and seat setup done\n";
build(1,sz,1);
//cout<<"build done\n";
rep(i,H+1) rep(j,W+1)
{
calc(i,j,1);
//cout<<"init "<<i<<" "<<j<<" done\n";
}
//cout<<st[1].cnt<<"\n\n";
}
int swap_seats(int a,int b)
{
a++,b++;
//cout<<"seat[a]: "<<seat[a].F<<" "<<seat[a].S<<"\n";
rep(i,4) calc(seat[a].F+dx[i],seat[a].S+dy[i],-1);
p[seat[a].F][seat[a].S]=b;
rep(i,4) calc(seat[a].F+dx[i],seat[a].S+dy[i],1);
//cout<<"a done\n\n";
//cout<<"seat[b]: "<<seat[b].F<<" "<<seat[b].S<<"\n";
rep(i,4) calc(seat[b].F+dx[i],seat[b].S+dy[i],-1);
p[seat[b].F][seat[b].S]=a;
rep(i,4) calc(seat[b].F+dx[i],seat[b].S+dy[i],1);
//cout<<"b done\n\n";
swap(seat[a],seat[b]);
return st[1].cnt;
}
/*
int main()
{
int h,w;
cin>>h>>w;
vector<int> r(h*w),c(h*w);
rep(i,h*w) cin>>r[i];
rep(i,h*w) cin>>c[i];
give_initial_chart(h,w,r,c);
int q;
cin>>q;
while(q--)
{
int a,b;
cin>>a>>b;
cout<<swap_seats(a,b)<<"\n";
}
}
*/
