## 1. Abridged Problem Statement

Given an `M × N` rectangular board (`1 ≤ M, N ≤ 200`) where some cells exist (`1`) and some are removed (`0`), place as many Guardians as possible on existing cells such that:

- No two Guardians are on the same cell or on edge-neighboring cells.
- Every existing cell is defended, meaning it either contains a Guardian or is edge-adjacent to one.

Output the maximum number of Guardians and any valid placement using:

- `G` for Guardian,
- `.` for empty existing cell,
- `#` for removed cell.

---

## 2. Detailed Editorial

### Graph interpretation

Treat every existing board cell as a vertex of a graph.

Connect two vertices by an edge if their cells share a side.

A Guardian attacks:

- its own cell,
- the four edge-neighboring cells.

Therefore:

- Two Guardians cannot be placed on adjacent cells, because they would attack each other.
- So the chosen Guardian cells must form an **independent set** in this graph.
- Every existing cell must be defended, so every vertex must either be chosen or adjacent to a chosen vertex. This means the chosen set must also be a **dominating set**.

We want the largest set of cells that is both independent and dominating.

---

### Key observation

Any **maximum independent set** is automatically dominating.

Why?

Suppose we have a maximum independent set `S`.

If there is some vertex `v` that is:

- not in `S`,
- not adjacent to any vertex in `S`,

then we could add `v` to `S`, and it would still be independent.

That contradicts the fact that `S` was maximum.

Therefore, every maximum independent set is dominating.

So the problem reduces to:

> Find a maximum independent set of the graph of existing cells.

---

### The graph is bipartite

The grid graph is bipartite using checkerboard coloring:

- Cells with `(row + col) % 2 == 0` go to the left part.
- Cells with `(row + col) % 2 == 1` go to the right part.

Every edge connects cells of opposite parity.

---

### König’s theorem

For bipartite graphs:

```text
size(maximum independent set) = number of vertices - size(minimum vertex cover)
```

And by König’s theorem:

```text
size(minimum vertex cover) = size(maximum matching)
```

So we can:

1. Build the bipartite graph.
2. Find a maximum matching using Hopcroft–Karp.
3. Recover a minimum vertex cover.
4. Take its complement to obtain a maximum independent set.
5. Place Guardians on those cells.

---

### Recovering the minimum vertex cover

After computing a maximum matching:

1. Start from all unmatched left-side vertices.
2. Traverse alternating paths:
   - from left to right along non-matching edges,
   - from right to left along matching edges.
3. Let:
   - `Z_L` be visited left vertices,
   - `Z_R` be visited right vertices.

Then a minimum vertex cover is:

```text
(left vertices not in Z_L) ∪ (right vertices in Z_R)
```

Therefore, the maximum independent set is its complement:

```text
(left vertices in Z_L) ∪ (right vertices not in Z_R)
```

The provided C++ implementation wraps this logic inside a Hopcroft–Karp class.

---

### Complexity

There are at most:

```text
V ≤ 40000
E ≤ about 80000
```

Hopcroft–Karp runs in:

```text
O(E sqrt(V))
```

which is suitable for the constraints.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/hopcroft_karp.hpp>

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;
};

class HopcroftKarp {
  private:
    int n, m;
    vector<int> dist;

    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for(int u = 0; u < n; u++) {
            if(inv_match[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }

        bool found = false;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int v: adj[u]) {
                int m = match[v];
                if(m == -1) {
                    found = true;
                } else if(dist[m] == -1) {
                    dist[m] = dist[u] + 1;
                    q.push(m);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        for(int v: adj[u]) {
            int m = match[v];
            if(m == -1 || (dist[m] == dist[u] + 1 && dfs(m))) {
                inv_match[u] = v;
                match[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }

  public:
    vector<int> match, inv_match;
    vector<vector<int>> adj;

    HopcroftKarp(int _n, int _m = -1) : n(_n), m(_m == -1 ? _n : _m) {
        adj.assign(n, vector<int>());
        clear(false);
    }

    void clear(bool clear_adj = true) {
        match.assign(m, -1);
        inv_match.assign(n, -1);
        if(clear_adj) {
            adj.assign(n, vector<int>());
        }
    }

    void add_edge(int u, int v) { adj[u].push_back(v); }

    int max_matching(bool shuffle_edges = false) {
        if(shuffle_edges) {
            for(int i = 0; i < n; i++) {
                shuffle(
                    adj[i].begin(), adj[i].end(),
                    mt19937(
                        chrono::steady_clock::now().time_since_epoch().count()
                    )
                );
            }
        }

        int ans = 0;
        while(bfs()) {
            for(int u = 0; u < n; u++) {
                if(inv_match[u] == -1 && dfs(u)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    vector<pair<int, int>> get_matching() {
        vector<pair<int, int>> matches;
        for(int u = 0; u < n; u++) {
            if(inv_match[u] != -1) {
                matches.emplace_back(u, inv_match[u]);
            }
        }
        return matches;
    }

    pair<vector<int>, vector<int>> minimum_vertex_cover() {
        // König: alternating-BFS from unmatched left vertices marks the
        // reachable set Z; cover = (Left \ Z) on the left side together with
        // (Right in Z) on the right side. Here dist[u] != -1 means u is in Z.

        vector<int> left_cover, right_cover;
        bfs();

        for(int u = 0; u < n; u++) {
            if(dist[u] == -1) {
                left_cover.push_back(u);
            }
        }

        for(int v = 0; v < m; v++) {
            if(match[v] != -1 && dist[match[v]] != -1) {
                right_cover.push_back(v);
            }
        }

        return {left_cover, right_cover};
    }

    pair<vector<int>, vector<int>> maximum_independent_set() {
        // The complement of a minimum vertex cover is a maximum independent
        // set (König), so keep exactly the vertices not in the cover.

        auto [left_cover, right_cover] = minimum_vertex_cover();
        vector<char> in_left_cover(n), in_right_cover(m);
        for(int u: left_cover) {
            in_left_cover[u] = 1;
        }

        for(int v: right_cover) {
            in_right_cover[v] = 1;
        }

        vector<int> left_set, right_set;
        for(int u = 0; u < n; u++) {
            if(!in_left_cover[u]) {
                left_set.push_back(u);
            }
        }

        for(int v = 0; v < m; v++) {
            if(!in_right_cover[v]) {
                right_set.push_back(v);
            }
        }

        return {left_set, right_set};
    }
};

using BipartiteMatching = HopcroftKarp;

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

void read() {
    cin >> m >> n;
    grid.assign(m, vector<int>(n));
    for(auto& row: grid) {
        cin >> row;
    }
}

void solve() {
    // A Guardian attacks its own cell and the four edge-neighbors. Two
    // Guardians may not stand on the same or neighboring cells (they would
    // kill each other), so the chosen cells form an independent set in the
    // grid graph. Every present cell must also be attacked by some Guardian,
    // i.e. the chosen set must be dominating. We want the largest such set.
    //
    // A maximum independent set is automatically dominating: if some cell
    // were neither chosen nor adjacent to a chosen cell, we could add it and
    // get a larger independent set, contradicting maximality. So the answer
    // is just the maximum independent set of the grid graph.
    //
    // The grid graph is bipartite under a checkerboard coloring, with edges
    // only between an even cell (i + j even) and an odd neighbor. By Koenig's
    // theorem the maximum independent set is the complement of a minimum
    // vertex cover, which we recover from a maximum matching: an even cell is
    // chosen iff it is not in the cover, and likewise for odd cells.

    vector<vector<int>> id(m, vector<int>(n, -1));
    int num_even = 0, num_odd = 0;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j]) {
                id[i][j] = ((i + j) & 1) ? num_odd++ : num_even++;
            }
        }
    }

    HopcroftKarp hk(num_even, num_odd);
    static const int di[] = {-1, 1, 0, 0};
    static const int dj[] = {0, 0, -1, 1};
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(grid[i][j] && ((i + j) & 1) == 0) {
                for(int d = 0; d < 4; d++) {
                    int ni = i + di[d], nj = j + dj[d];
                    if(ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj]) {
                        hk.add_edge(id[i][j], id[ni][nj]);
                    }
                }
            }
        }
    }

    hk.max_matching();
    auto [even_set, odd_set] = hk.maximum_independent_set();

    vector<char> even_chosen(num_even), odd_chosen(num_odd);
    for(int u: even_set) {
        even_chosen[u] = 1;
    }

    for(int v: odd_set) {
        odd_chosen[v] = 1;
    }

    vector<string> out(m, string(n, '#'));
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(!grid[i][j]) {
                continue;
            }

            bool chosen =
                ((i + j) & 1) ? odd_chosen[id[i][j]] : even_chosen[id[i][j]];
            out[i][j] = chosen ? 'G' : '.';
        }
    }

    cout << even_set.size() + odd_set.size() << '\n';
    for(auto& row: out) {
        cout << row << '\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
from collections import deque


def hopcroft_karp(adj, left_size, right_size):
    """
    Computes maximum bipartite matching.

    adj[u] contains all right-side vertices adjacent to left-side vertex u.

    Returns:
        pair_u: pair_u[u] = matched right vertex of left u, or -1
        pair_v: pair_v[v] = matched left vertex of right v, or -1
    """

    pair_u = [-1] * left_size      # Matching from left to right.
    pair_v = [-1] * right_size     # Matching from right to left.
    dist = [-1] * left_size        # BFS levels for left vertices.

    def bfs():
        """
        Builds BFS layers starting from all unmatched left vertices.
        Returns True if there may be an augmenting path.
        """

        q = deque()                # Queue for BFS.

        for u in range(left_size):
            if pair_u[u] == -1:    # Unmatched left vertices are sources.
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1       # Matched vertices initially unvisited.

        found = False              # Whether we reached an unmatched right vertex.

        while q:
            u = q.popleft()

            for v in adj[u]:
                matched_left = pair_v[v]

                if matched_left == -1:
                    # We found an edge to an unmatched right vertex,
                    # so an augmenting path exists.
                    found = True
                elif dist[matched_left] == -1:
                    # Continue along the alternating path.
                    dist[matched_left] = dist[u] + 1
                    q.append(matched_left)

        return found

    def dfs(u):
        """
        Attempts to find an augmenting path from left vertex u,
        respecting BFS layers.
        """

        for v in adj[u]:
            matched_left = pair_v[v]

            if matched_left == -1 or (
                dist[matched_left] == dist[u] + 1 and dfs(matched_left)
            ):
                pair_u[u] = v
                pair_v[v] = u
                return True

        # Mark as unusable in this phase.
        dist[u] = -1
        return False

    matching_size = 0

    while bfs():
        for u in range(left_size):
            if pair_u[u] == -1:
                if dfs(u):
                    matching_size += 1

    return pair_u, pair_v


def maximum_independent_set(adj, pair_u, pair_v, left_size, right_size):
    """
    Given a maximum matching, computes a maximum independent set
    in a bipartite graph.

    Uses König's theorem:
        maximum independent set = complement of minimum vertex cover.

    Minimum vertex cover is obtained by alternating BFS from unmatched
    left vertices.
    """

    visited_left = [False] * left_size
    visited_right = [False] * right_size

    q = deque()

    # Start from all unmatched left vertices.
    for u in range(left_size):
        if pair_u[u] == -1:
            visited_left[u] = True
            q.append(u)

    while q:
        u = q.popleft()

        # From left side, traverse only non-matching edges.
        for v in adj[u]:
            if pair_u[u] == v:
                continue

            if not visited_right[v]:
                visited_right[v] = True

                # From right side, traverse the matching edge if it exists.
                matched_left = pair_v[v]
                if matched_left != -1 and not visited_left[matched_left]:
                    visited_left[matched_left] = True
                    q.append(matched_left)

    # Minimum vertex cover:
    #   left not visited + right visited
    #
    # Maximum independent set is complement:
    #   left visited + right not visited
    left_set = [u for u in range(left_size) if visited_left[u]]
    right_set = [v for v in range(right_size) if not visited_right[v]]

    return left_set, right_set


def main():
    data = sys.stdin.read().split()

    if not data:
        return

    it = iter(data)

    m = int(next(it))  # Number of rows.
    n = int(next(it))  # Number of columns.

    grid = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            grid[i][j] = int(next(it))

    # id_cell[i][j] stores the id of this cell in its bipartite side.
    id_cell = [[-1] * n for _ in range(m)]

    left_count = 0
    right_count = 0

    # Assign IDs to existing cells according to checkerboard parity.
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                if (i + j) % 2 == 0:
                    id_cell[i][j] = left_count
                    left_count += 1
                else:
                    id_cell[i][j] = right_count
                    right_count += 1

    # Adjacency list from even-parity cells to odd-parity cells.
    adj = [[] for _ in range(left_count)]

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Build graph edges between neighboring existing cells.
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1 and (i + j) % 2 == 0:
                u = id_cell[i][j]

                for di, dj in directions:
                    ni = i + di
                    nj = j + dj

                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                        v = id_cell[ni][nj]
                        adj[u].append(v)

    # Python recursion depth may need to be increased for DFS.
    sys.setrecursionlimit(1_000_000)

    # Compute maximum matching.
    pair_u, pair_v = hopcroft_karp(adj, left_count, right_count)

    # Compute maximum independent set.
    left_set, right_set = maximum_independent_set(
        adj, pair_u, pair_v, left_count, right_count
    )

    chosen_left = [False] * left_count
    chosen_right = [False] * right_count

    for u in left_set:
        chosen_left[u] = True

    for v in right_set:
        chosen_right[v] = True

    # Build output grid.
    output = [['#'] * n for _ in range(m)]

    guardian_count = len(left_set) + len(right_set)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                output[i][j] = '#'
            else:
                if (i + j) % 2 == 0:
                    chosen = chosen_left[id_cell[i][j]]
                else:
                    chosen = chosen_right[id_cell[i][j]]

                output[i][j] = 'G' if chosen else '.'

    result = [str(guardian_count)]

    for row in output:
        result.append(''.join(row))

    sys.stdout.write('\n'.join(result))


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

---

## 5. Compressed Editorial

Model existing cells as vertices of a graph, with edges between edge-neighboring cells.

A valid Guardian placement cannot contain adjacent cells, so it is an independent set. Since every cell must be protected, it must also dominate the graph. However, every maximum independent set is automatically dominating: otherwise, an undominated vertex could be added, contradicting maximality.

Thus, find a maximum independent set of the grid graph.

The grid graph is bipartite by checkerboard parity. In a bipartite graph:

```text
maximum independent set = complement of minimum vertex cover
```

By König’s theorem, a minimum vertex cover can be found from a maximum matching.

Algorithm:

1. Put cells with even `(i + j)` parity on the left, odd parity on the right.
2. Add edges between neighboring existing cells.
3. Run Hopcroft–Karp to get a maximum matching.
4. Recover minimum vertex cover using alternating BFS from unmatched left vertices.
5. Take its complement as the maximum independent set.
6. Place Guardians on those cells.

Complexity:

```text
O(E sqrt(V))
```

with `V ≤ 40000`, suitable for the problem constraints.