#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 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,tags[N];
bool cur=0;
void give_tag(int t,int id)
{
st[id].tag+=t;
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].mn=tags[l];
st[id].cnt=1;
st[id].tag=0;
}
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 update(int x,int y,int t)
{
if(x==y) return;
if(!cur)
{
tags[x]+=t;
tags[y]-=t;
}
else modify(1,sz,x,y-1,t,1);
}
void calc(int x,int y,int t)
{
int tmp[4]={p[x][y],p[x+1][y],p[x][y+1],p[x+1][y+1]};
sort(tmp,tmp+4);
update(tmp[0],tmp[1],t);
update(tmp[2],tmp[3],t);
}
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};
}
rep(i,H+1) rep(j,W+1) calc(i,j,1);
rep1(i,sz) tags[i]+=tags[i-1];
build(1,sz,1);
cur=1;
}
int swap_seats(int a,int b)
{
a++,b++;
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);
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);
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";
}
}
*/
