#include <bits/stdc++.h>
//#include "horses.h"
using namespace std;
#define ll long long
#define vb vector<bool>
#define pb push_back
#define ff(aa, bb, cc) for(int aa = bb; aa < cc; aa++)
#define vl vector<ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define ed "\n"
#define all(aaa) aaa.begin(), aaa.end()
#define rall(aaa) aaa.rbegin(), aaa.rend()
ll MOD = 1e9+7;
set<pair<pll, pll>> st;
vector<vl> grid;
map<ll, pll> pos;
ll h, w;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
h = H;
w = W;
grid = vector<vl>(H, vl(W));
ff(i, 0, H*W){
pos[i] = {R[i], C[i]};
grid[R[i]][C[i]] = i;
}
}
ll c = 0;
void cases(pll ti, pll bd, set<ll> seats, ll orient){
//cout << ti.fi << " " << ti.se << " " << bd.fi << " " << bd.se << ed;
if(ti.fi < 0 || ti.se < 0 || bd.fi >= h || bd.se >= w){
//cout << "OUT" << ed;
return;
}
if(orient == 0){
//cout << "BASE" << ed;
seats.insert(0);
}
else{
//cout << "AAAAA" << ed;
ll sz = st.size();
//cout << "AAAAA" << ed;
st.insert({ti, bd});
//cout << "AAAAA" << ed;
//cout << st.size() << " " << sz << ed;
if(st.size() == sz){
//cout << "TRASH" << ed;
return;
}
//cout << "AFTER" << ed;
}
//{y, x}
pll td = {ti.fi, bd.se}, bi = {bd.fi, ti.se};
//cout << "CHECK " << orient << ed;
//cout << ti.fi << " " <<ti.se << " " << bd.fi << " " << bd.se << ed;
if(orient == 1){
// cout << "C1" << " ";
ff(i, ti.fi, bi.fi+1){
seats.insert(grid[i][ti.se]);
}
}
else if(orient == 2){
//cout << "C2" << " ";
ff(i, td.fi, bd.fi+1){
seats.insert(grid[i][td.se]);
}
}
else if(orient == 3){
//cout << "C3" << " ";
ff(i, ti.se, td.se+1){
seats.insert(grid[ti.fi][i]);
}
}
else if(orient == 4){
//cout << "C4" << " ";
ff(i, bi.se, bd.se+1){
seats.insert(grid[bi.fi][i]);
}
}
if(seats.size()-1 == *seats.rbegin()){
//cout << "PLUS" << ed;
c++;
}
//cout << ed;
set<ll> s = seats;
cases({ti.fi, ti.se-1}, bd, s, 1);
s = seats;
cases(ti, {bd.fi, bd.se+1}, s, 2);
s = seats;
cases({ti.fi-1, ti.se}, bd, s, 3);
s = seats;
cases(ti, {bd.fi+1, bd.se}, s, 4);
}
int swap_seats(int a, int b){
st.clear();
ll x1 = pos[a].se, y1 = pos[a].fi, x2 = pos[b].se, y2 = pos[b].fi;
swap(grid[y1][x1], grid[y2][x2]);
swap(pos[a], pos[b]);
ll stx = pos[0].se, sty = pos[0].fi;
pll coords = pos[0];
c = 0;
set<ll> s;
cases(coords, coords, s, 0);
return c;
}
/*
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
}
*/
