OI XXXIII - dos (Pool)

// https://szkopul.edu.pl/problemset/problem/xK8Nwxsp_J6k2H63B_YJRWtH/site/?key=statement

#include <bits/stdc++.h>

// using namespace std;

// #define GARY_DBG
#define GARY_LIB

// #define int long long

constexpr int sizik = 1007;
constexpr int INF = 2 * 1001 * 1000;

#define ar std::array
#define pr std::pair

namespace SegTree {

constexpr int MAX_NODES = 6000000;
constexpr int INF = 1e9;
constexpr int L_VAL = 0;

struct Node {
    int l, r;
    int cnt;
    int wyn;
} tree[MAX_NODES];

int node_ptr = 0;
int root = 0;

int get_cnt(int u) {
    return u ? tree[u].cnt : 0;
}
int get_wyn(int u) {
    return u ? tree[u].wyn : L_VAL;
}

void update(int& u, int tl, int tr, int pos, int delta) {
    if (!u) {
        u = ++node_ptr;
    }

    if (tl == tr) {
        tree[u].cnt += delta;
        if (tree[u].cnt > 0) {
            tree[u].wyn = tl + tree[u].cnt - 1;
        } else {
            tree[u].wyn = L_VAL;
        }
        return;
    }

    int tm = tl + (tr - tl) / 2;

    if (pos <= tm)
        update(tree[u].l, tl, tm, pos, delta);
    else
        update(tree[u].r, tm + 1, tr, pos, delta);

    int left_cnt = get_cnt(tree[u].l);
    int right_cnt = get_cnt(tree[u].r);
    int left_wyn = get_wyn(tree[u].l);
    int right_wyn = get_wyn(tree[u].r);

    tree[u].cnt = left_cnt + right_cnt;

    int right_candidate = right_wyn;
    int left_candidate = (left_wyn == L_VAL) ? L_VAL : left_wyn + right_cnt;
    tree[u].wyn = std::max(left_candidate, right_candidate);
}

void insert(int x) {
    update(root, L_VAL, INF, x, +1);
}
void erase_one(int x) {
    update(root, L_VAL, INF, x, -1);
}
int get_max() {
    return get_wyn(root);
}

} // namespace SegTree

constexpr int NIC = 0;
constexpr int PRZESZKODA = 1;
constexpr int WOLNE_POLE = 2;
constexpr int FORT = 3;

// [y][x]
int mapka[sizik][sizik];
int bfs_map[sizik][sizik];
ar<std::bitset<sizik>, sizik> visited;

bool is_przeszkoda(int y, int x) {
    return mapka[y][x] == PRZESZKODA || mapka[y][x] == NIC;
}

void bfs() {
    std::queue<ar<int, 3>> q;
    q.push({1, 1, 0});
    while (!q.empty()) {
        auto [y, x, d] = q.front();
        q.pop();

        if (visited[y][x]) continue;
        visited[y][x] = true;

        bfs_map[y][x] = d;

        if (!is_przeszkoda(y - 1, x)) {
            q.push({y - 1, x, d + 1});
        }
        if (!is_przeszkoda(y + 1, x)) {
            q.push({y + 1, x, d + 1});
        }
        if (!is_przeszkoda(y, x - 1)) {
            q.push({y, x - 1, d + 1});
        }
        if (!is_przeszkoda(y, x + 1)) {
            q.push({y, x + 1, d + 1});
        }
    }
}

// SegTree::SegTree ds;
int elements_added = 0;

void update(int y, int x) {
    if (mapka[y][x] == FORT) {
        SegTree::erase_one(bfs_map[y][x]);
        elements_added--;
        mapka[y][x] = WOLNE_POLE;
    } else if (mapka[y][x] == WOLNE_POLE) {
        SegTree::insert(bfs_map[y][x]);
        elements_added++;
        mapka[y][x] = FORT;
    } else {
        std::cout << "NOT GOOD\n";
    }
}

void ans_q() {
    // return ds.query();
    if (elements_added == 0) {
        std::cout << "0\n";
        return;
    }
    int64_t ans = SegTree::get_max();
    std::cout << ans << '\n';
}

void solve() {
    int n, q;
    std::cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char c;
            std::cin >> c;

            if (c == '#') {
                mapka[i][j] = PRZESZKODA;
            } else if (c == 'Z' || c == '.') {
                mapka[i][j] = WOLNE_POLE;
            } else {
                assert(c == 'F');
                mapka[i][j] = FORT;
            }
        }
    }

    bfs();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (mapka[i][j] == FORT) {
                SegTree::insert(bfs_map[i][j]);
                elements_added++;
            }
        }
    }

    ans_q();

    for (; q > 0; q--) {
        int x, y;
        std::cin >> y >> x;

        update(y, x);

        ans_q();
    }
}

int32_t main() {
#ifndef GARY_DBG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}