#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
class DisjointSet{
private:
vector<int> size;
vector<int> parent;
vector<int> min_row;
vector<int> max_row;
vector<int> min_column;
vector<int> max_column;
public:
DisjointSet(int H, int W) {
size = parent = min_row = max_row = min_column = max_column = vector<int>(H * W + 25);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int idx = i * W + j;
size[idx] = 1;
parent[idx] = idx;
min_row[idx] = max_row[idx] = i;
min_column[idx] = max_column[idx] = j;
}
}
}
int root(int x) {
if (x == parent[x]) return x;
return parent[x] = root(parent[x]);
}
void join(int a, int b) {
a = root(a);
b = root(b);
if (a == b) return;
if (size[a] < size[b]) swap(a, b);
size[a] += size[b];
max_row[a] = max(max_row[a], max_row[b]);
min_row[a] = min(min_row[a], min_row[b]);
max_column[a] = max(max_column[a], max_column[b]);
min_column[a] = min(min_column[a], min_column[b]);
parent[b] = a;
}
int is_cute(int idx, int tamanho_total) {
const int s = root(idx);
if(size[s] != tamanho_total) return 0;
const int rec = (max_row[s] - min_row[s] + 1) * (max_column[s] - min_column[s] + 1);
return rec == tamanho_total;
}
};
int r, c;
vector<pair<int, int>> where;
vector<vector<int>> mat;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
ios::sync_with_stdio(0);
cin.tie(0);
r = H;
c = W;
where.resize(r * c);
mat = vector<vector<int>>(r, vector<int>(c));
for (int i = 0; i < r * c; i++) {
where[i] = {R[i], C[i]};
mat[R[i]][C[i]] = i;
}
}
const int dr[] = {+1, -1, +0, +0};
const int dc[] = {+0, +0, +1, -1};
int solve() {
DisjointSet DSU(r, c);
int res = 0;
const int sr = where[0].first;
const int sc = where[0].second;
for (int i = 0; i < r * c; i++) {
const int linha = where[i].first;
const int coluna = where[i].second;
for (int x = 0; x < 4; x++) {
if (linha + dr[x] < 0 || linha + dr[x] >= r || coluna + dc[x] < 0 || coluna + dc[x] >= c) continue;
if (mat[linha + dr[x]][coluna + dc[x]] >= i) continue;
DSU.join(linha * c + coluna, (linha + dr[x]) * c + coluna + dc[x]);
}
res += DSU.is_cute(sr * c + sc, i + 1);
}
return res;
}
int swap_seats(int a, int b) {
swap(mat[where[a].first][where[a].second], mat[where[b].first][where[b].second]);
swap(where[a], where[b]);
return solve();
}
