## 1. Abridged problem statement

We are given an `N × M` grid of digits `0..9`. Each mafia leader owns one 4-connected region, and neighboring leaders always have different digits. Therefore, each maximal 4-connected component of equal digits is one leader’s territory.

A leader is **big** if its territory contains at least `K` cells.

A cell is **dangerous** if either:

1. it belongs to a big leader, or
2. there exists a big leader such that every path from this cell to the border of the grid must pass through that big leader’s territory.

Find the total number of dangerous cells.

Constraints:

```text
1 ≤ N, M ≤ 500
1 ≤ K ≤ 250000
```

---

## 2. Detailed editorial

### Key observation: compress equal-digit components

Because adjacent territories cannot have the same digit, every maximal 4-connected component of equal digits corresponds to exactly one mafia leader.

So first, we flood-fill the grid and assign each cell a component ID.

For every component we store:

- its size,
- whether it touches the border,
- which other components are adjacent to it.

This gives us a graph:

- each vertex is a mafia leader/component,
- edges connect neighboring components.

We also add one extra vertex called `OUTSIDE`.

Every component touching the grid border is connected to `OUTSIDE`.

Now a path from a cell to the border corresponds to a path in this component graph from that cell’s component to `OUTSIDE`.

---

### Dangerous cells in graph terms

A component is immediately dangerous if it is big.

Now consider a non-big component `C`.

It is dangerous if there exists a big component `B` such that every path from `C` to `OUTSIDE` passes through `B`.

In graph theory, this means:

> `B` is an articulation point separating `C` from `OUTSIDE`.

So the task becomes:

- build the component graph,
- root a DFS at `OUTSIDE`,
- find articulation relationships,
- whenever a big component separates a DFS subtree from `OUTSIDE`, all components in that subtree are dangerous.

---

### Tarjan articulation DFS

Run Tarjan’s DFS from `OUTSIDE`.

For each vertex `u`, compute:

- `disc[u]`: DFS discovery time,
- `low[u]`: smallest discovery time reachable from `u`’s subtree using at most one back edge.

For a DFS tree edge `u -> v`, if:

```text
low[v] >= disc[u]
```

then `v`’s subtree cannot reach an ancestor of `u` without passing through `u`.

Therefore, if `u` is a big component, then every component in `v`’s DFS subtree is dangerous.

---

### Efficiently marking whole DFS subtrees

DFS discovery times form contiguous intervals for subtrees.

If subtree rooted at `v` has Euler interval:

```text
[disc[v], subtree_end[v]]
```

then all components in that interval should be marked dangerous.

Instead of marking each component one by one, use a difference array:

```text
diff[disc[v]] += 1
diff[subtree_end[v] + 1] -= 1
```

After DFS, prefix-sum the difference array.

A component is dominated by some big separator if its discovery time has positive prefix value.

---

### Final answer

For every component:

- if it is big, add its size,
- else if it is marked dominated by a big articulation component, add its size.

---

### Correctness sketch

Each grid path corresponds to a path in the component graph, and vice versa at the component level. Reaching the grid border is equivalent to reaching the virtual `OUTSIDE` vertex.

A component is dangerous due to a big leader exactly when all paths from it to `OUTSIDE` pass through that big leader. This is exactly the definition of being separated by an articulation point.

Tarjan’s condition `low[v] >= disc[u]` correctly identifies when the DFS subtree of `v` is separated from `OUTSIDE` by `u`. Therefore, marking such subtrees for every big `u` marks exactly all components that cannot escape without passing through a big component.

Finally, all cells in big components are dangerous by definition, so summing sizes of big or marked components gives the required answer.

---

### Complexity

Let `S = N × M`.

Flood fill takes `O(S)` grid visits.

The component graph has `O(S)` vertices and edges.

Tarjan DFS is `O(S)`.

The provided C++ solution uses `set` for neighbor lists, so practically it is `O(S log S)` in the worst case due to insertions, but still easily fits.

Memory usage is `O(S)`.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k;
vector<string> grid;

vector<vector<int>> comp_id;
vector<int> comp_size;
vector<char> comp_touches_border;
vector<set<int>> comp_neighbours;

void read() {
    cin >> n >> m >> k;
    grid.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> grid[i];
    }
}

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

void label_zones() {
    comp_id.assign(n, vector<int>(m, -1));
    comp_size.clear();
    comp_touches_border.clear();
    comp_neighbours.clear();

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(comp_id[i][j] != -1) {
                continue;
            }

            int cid = comp_size.size();
            comp_size.push_back(0);
            comp_touches_border.push_back(0);
            comp_neighbours.emplace_back();

            char color = grid[i][j];
            queue<pair<int, int>> q;
            q.push({i, j});
            comp_id[i][j] = cid;

            while(!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                comp_size[cid]++;
                if(x == 0 || x == n - 1 || y == 0 || y == m - 1) {
                    comp_touches_border[cid] = 1;
                }

                for(int d = 0; d < 4; d++) {
                    int nx = x + di[d], ny = y + dj[d];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        continue;
                    }

                    if(grid[nx][ny] == color) {
                        if(comp_id[nx][ny] == -1) {
                            comp_id[nx][ny] = cid;
                            q.push({nx, ny});
                        }
                    } else if(comp_id[nx][ny] != -1) {
                        comp_neighbours[cid].insert(comp_id[nx][ny]);
                        comp_neighbours[comp_id[nx][ny]].insert(cid);
                    }
                }
            }
        }
    }
}

vector<char> dominated_by_big_zone(const vector<char>& is_big) {
    int num_comps = comp_size.size();
    int outside = num_comps;
    int V = num_comps + 1;

    vector<vector<int>> adj(V);
    for(int c = 0; c < num_comps; c++) {
        for(int u: comp_neighbours[c]) {
            adj[c].push_back(u);
        }
        if(comp_touches_border[c]) {
            adj[c].push_back(outside);
            adj[outside].push_back(c);
        }
    }

    vector<int> disc(V, -1), low(V, 0), in_t(V, 0);
    vector<int> dom(V + 2, 0);
    vector<tuple<int, int, int>> st;
    st.reserve(V);
    int timer = 0;

    st.emplace_back(outside, 0, -1);
    disc[outside] = low[outside] = in_t[outside] = timer++;

    while(!st.empty()) {
        auto& [u, it, p] = st.back();
        if(it < (int)adj[u].size()) {
            int v = adj[u][it++];
            if(v == p) {
                continue;
            }

            if(disc[v] == -1) {
                disc[v] = low[v] = in_t[v] = timer++;
                st.emplace_back(v, 0, u);
            } else {
                low[u] = min(low[u], disc[v]);
            }
        } else {
            int u_low = low[u], u_in = in_t[u], u_out = timer - 1, parent = p;
            st.pop_back();
            if(parent == -1) {
                continue;
            }

            low[parent] = min(low[parent], u_low);
            if(u_low >= disc[parent] && parent < num_comps && is_big[parent]) {
                dom[u_in] += 1;
                dom[u_out + 1] -= 1;
            }
        }
    }

    for(int t = 1; t < timer; t++) {
        dom[t] += dom[t - 1];
    }

    vector<char> result(num_comps, 0);
    for(int c = 0; c < num_comps; c++) {
        result[c] = dom[in_t[c]] > 0;
    }
    return result;
}

void solve() {
    // If we group same-color 4-connected cells into zones, the resulting
    // structure is planar. A cell is dangerous iff it is part of a big zone
    // (size >= K) or lies strictly inside a face of some big zone, i.e.
    // there is a big zone X such that every escape path from the cell to
    // the border passes through X. Equivalently, X is an articulation point
    // separating the cell's zone from a virtual OUTSIDE node in the zone
    // adjacency graph.
    //
    // We flood fill once to label every zone with a component id and to
    // record its size, whether it touches the border, and the set of
    // neighbouring zones. Then we build the zone graph with an extra
    // OUTSIDE node joined to every border-touching zone and run Tarjan's
    // articulation point algorithm rooted at OUTSIDE. Whenever a DFS-tree
    // child v of u finishes with low[v] >= disc[u] and u is a big zone, u
    // cuts the entire subtree of v from OUTSIDE, so every zone in v's
    // subtree is dangerous. We mark each such subtree as a +1/-1 range on
    // the Euler-tour index and prefix-sum at the end.

    label_zones();

    int num_comps = comp_size.size();
    vector<char> is_big(num_comps, 0);
    for(int c = 0; c < num_comps; c++) {
        is_big[c] = comp_size[c] >= k;
    }

    auto dominated = dominated_by_big_zone(is_big);

    int ans = 0;
    for(int c = 0; c < num_comps; c++) {
        if(is_big[c] || dominated[c]) {
            ans += comp_size[c];
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def solve():
    # Read all input lines.
    data = sys.stdin.read().strip().split()

    # If input is empty, do nothing.
    if not data:
        return

    # First three tokens are N, M, K.
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])

    # Next n tokens are grid rows.
    rows = data[3:3 + n]

    # Flatten the grid into one string for simpler indexing.
    # Cell (r, c) has flat index r * m + c.
    flat = ''.join(rows)

    # Total number of cells.
    total = n * m

    # comp_id[idx] is the component ID of cell idx.
    comp_id = [-1] * total

    # Size of each component.
    comp_size = []

    # Whether each component touches the grid border.
    touches_border = []

    # Four movement directions.
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    # Flood-fill all same-digit connected components.
    for start in range(total):
        # Skip already labeled cells.
        if comp_id[start] != -1:
            continue

        # New component ID.
        cid = len(comp_size)

        # Digit/color of this component.
        color = flat[start]

        # Mark starting cell.
        comp_id[start] = cid

        # Stack for iterative DFS flood fill.
        stack = [start]

        # Component size counter.
        size = 0

        # Whether this component touches the border.
        border = False

        # Process all cells in this component.
        while stack:
            # Pop one cell.
            v = stack.pop()

            # Count it.
            size += 1

            # Convert flat index to row and column.
            r = v // m
            c = v % m

            # Check whether it is on the border.
            if r == 0 or r == n - 1 or c == 0 or c == m - 1:
                border = True

            # Explore four neighbors.
            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                # Ignore outside-grid positions.
                if nr < 0 or nr >= n or nc < 0 or nc >= m:
                    continue

                # Neighbor flat index.
                to = nr * m + nc

                # Same digit and unvisited means it belongs to this component.
                if flat[to] == color and comp_id[to] == -1:
                    comp_id[to] = cid
                    stack.append(to)

        # Store component information.
        comp_size.append(size)
        touches_border.append(border)

    # Number of components.
    num_comps = len(comp_size)

    # Build component graph.
    outside = num_comps
    vertex_count = num_comps + 1

    # Use a set to avoid duplicate edges between the same components.
    edge_set = set()

    # Scan horizontal and vertical neighboring cell pairs.
    for r in range(n):
        base = r * m
        for c in range(m):
            idx = base + c
            a = comp_id[idx]

            # Right neighbor.
            if c + 1 < m:
                b = comp_id[idx + 1]
                if a != b:
                    x, y = (a, b) if a < b else (b, a)
                    edge_set.add(x * num_comps + y)

            # Down neighbor.
            if r + 1 < n:
                b = comp_id[idx + m]
                if a != b:
                    x, y = (a, b) if a < b else (b, a)
                    edge_set.add(x * num_comps + y)

    # Adjacency list including OUTSIDE vertex.
    adj = [[] for _ in range(vertex_count)]

    # Add component-component edges.
    for code in edge_set:
        a = code // num_comps
        b = code % num_comps
        adj[a].append(b)
        adj[b].append(a)

    # Connect border-touching components to OUTSIDE.
    for c in range(num_comps):
        if touches_border[c]:
            adj[c].append(outside)
            adj[outside].append(c)

    # Mark big components.
    is_big = [size >= k for size in comp_size]

    # Tarjan arrays.
    disc = [-1] * vertex_count
    low = [0] * vertex_count

    # Difference array over DFS order.
    diff = [0] * (vertex_count + 2)

    # DFS timer.
    timer = 0

    # Start DFS from OUTSIDE.
    disc[outside] = low[outside] = timer
    timer += 1

    # Stack frame format:
    # [vertex, next_neighbor_index, parent]
    stack = [[outside, 0, -1]]

    # Iterative Tarjan DFS.
    while stack:
        u, it, parent = stack[-1]

        # If there are still neighbors to process.
        if it < len(adj[u]):
            # Take next neighbor.
            v = adj[u][it]

            # Advance iterator in the top stack frame.
            stack[-1][1] += 1

            # Ignore tree edge to parent.
            if v == parent:
                continue

            # Tree edge to an unvisited vertex.
            if disc[v] == -1:
                disc[v] = low[v] = timer
                timer += 1
                stack.append([v, 0, u])

            # Back edge to an already visited vertex.
            else:
                low[u] = min(low[u], disc[v])

        # All neighbors processed; finish u.
        else:
            # Entry time of u's subtree.
            u_in = disc[u]

            # Since DFS preorder intervals are contiguous,
            # the last discovered vertex so far is subtree end.
            u_out = timer - 1

            # Final low-link value.
            u_low = low[u]

            # Remove u from stack.
            stack.pop()

            # OUTSIDE has no parent.
            if parent == -1:
                continue

            # Propagate low-link value upward.
            low[parent] = min(low[parent], u_low)

            # If parent is a big component and separates u's subtree,
            # mark that whole subtree as dangerous.
            if parent < num_comps and is_big[parent] and u_low >= disc[parent]:
                diff[u_in] += 1
                diff[u_out + 1] -= 1

    # Prefix sum of difference array.
    for i in range(1, timer):
        diff[i] += diff[i - 1]

    # Count dangerous cells.
    answer = 0

    for c in range(num_comps):
        # Component is dangerous if it is big or dominated by a big separator.
        if is_big[c] or diff[disc[c]] > 0:
            answer += comp_size[c]

    # Output answer.
    print(answer)


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed editorial

Compress the grid into maximal 4-connected equal-digit components. Each component is one leader. Record its size and whether it touches the border.

Build a graph of components. Add a virtual `OUTSIDE` node connected to every border-touching component. A grid cell can escape Berland iff its component can reach `OUTSIDE`.

A component is dangerous if it is big, or if some big component lies on every path from it to `OUTSIDE`. In the component graph, this means the big component is an articulation point separating that component from `OUTSIDE`.

Run Tarjan DFS rooted at `OUTSIDE`. For every DFS tree edge `u -> v`, if:

```text
low[v] >= disc[u]
```

then `u` separates the subtree of `v` from `OUTSIDE`. If `u` is big, mark the whole subtree of `v` dangerous. Use DFS discovery intervals and a difference array to mark subtrees efficiently.

Finally, sum sizes of all components that are either big or marked dangerous.