//qoj2743
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int dx[5] = {0, 0, -1, 1, 0}, dy[5] = {0, -1, 0, 0, 1};
int n, m, mx;
vector<int> a[N];
pair<int, int> pos[N];

int t[N*4], tag[N*4], cnt[N*4];
void psd(int p){
    t[p<<1] += tag[p];
    t[p<<1|1] += tag[p];
    tag[p<<1] += tag[p];
    tag[p<<1|1] += tag[p];
    tag[p] = 0;
}
void upd(int p){
    if(t[p<<1] < t[p<<1|1]){
        t[p] = t[p<<1];
        cnt[p] = cnt[p<<1];
    } else if(t[p<<1] > t[p<<1|1]){
        t[p] = t[p<<1|1];
        cnt[p] = cnt[p<<1|1];
    } else {
        t[p] = t[p<<1];
        cnt[p] = cnt[p<<1] + cnt[p<<1|1];
    }
}
void build(int p, int l, int r){
    // printf("%d %d %d\n", p, l, r);
    if(l == r){
        t[p] = 1e9;
        cnt[p] = 1;
    } else {
        int mid = l + r >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);
        upd(p);
    }
}
void add(int p, int l, int r, int ql, int qr, int v){
    // if(p == 1) printf("%d %d %d\n", ql, qr, v);
    if(qr < l || r < ql){
        return;
    } else if(ql <= l && r <= qr){
        t[p] += v;
        tag[p] += v;
    } else {
        int mid = l + r >> 1;
        psd(p);
        add(p<<1, l, mid, ql, qr, v);
        add(p<<1|1, mid+1, r, ql, qr, v);
        upd(p);
    }
}

void upd(int x, int y, int op){
    add(1, 1, mx, a[x][y], min(a[x-1][y], a[x][y-1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x+1][y], a[x][y-1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x-1][y], a[x][y+1])-1, op);
    add(1, 1, mx, a[x][y], min(a[x+1][y], a[x][y+1])-1, op);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    n = H;
    m = W;
    mx = n * m;
    build(1, 1, mx);
    for(int i = 0; i <= m + 1; ++ i){
        a[0].push_back(mx + 1);
        a[n+1].push_back(mx + 1);
    }
    for(int i = 1; i <= n; ++ i){
        a[i].resize(m + 2);
        a[i][0] = a[i][m+1] = mx + 1;
    }
    for(int i = 0; i < mx; ++ i){
        a[R[i]+1][C[i]+1] = i + 1;
        pos[i+1] = make_pair(R[i] + 1, C[i] + 1);
    }
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j){
            // printf("%d ", a[i][j]);
            upd(i, j, 1);
        }
        // puts("");
    }
}

int swap_seats(int aa, int bb){
    ++ aa;
    ++ bb;
    int xa = pos[aa].first, ya = pos[aa].second;
    int xb = pos[bb].first, yb = pos[bb].second;
    vector<pair<int, int> > cg;
    for(int i = 0; i < 5; ++ i){
        int xx = xa + dx[i], yy = ya + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            cg.push_back(make_pair(xx, yy));
        }
        xx = xb + dx[i], yy = yb + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m){
            cg.push_back(make_pair(xx, yy));
        }
    }
    sort(cg.begin(), cg.end());
    for(int i = 0; i < cg.size(); ++ i){
        if(!i || cg[i] != cg[i-1]){
            upd(cg[i].first, cg[i].second, -1);
        }
    }
    swap(a[xa][ya], a[xb][yb]);
    swap(pos[aa], pos[bb]);
    for(int i = 0; i < cg.size(); ++ i){
        if(!i || cg[i] != cg[i-1]){
            upd(cg[i].first, cg[i].second, 1);
        }
    }
    return cnt[1];
}

#ifndef ONLINE_JUDGE
int main(){
    // give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1, 1, 2, 2});
    // printf("%d\n", swap_seats(0, 5));
    // printf("%d\n", swap_seats(0, 5));
    give_initial_chart(1, 5, {0, 0, 0, 0, 0}, {0, 1, 2, 3, 4});
    printf("%d\n", swap_seats(0, 1));
    printf("%d\n", swap_seats(0, 3));
    printf("%d\n", swap_seats(4, 0));
    // give_initial_chart(3, 3, {2, 1, 0, 0, 0, 2, 1, 1, 2}, {2, 2, 2, 1, 0, 1, 1, 0, 0});
    // printf("%d\n", cnt[1]);
    // printf("%d\n", swap_seats(6, 0));
    return 0;
}
#endif