<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

234. Black-White King Strikes Back
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



An irrecoverable event happened today's morning in the Chess World. Black King was killed. Of course, a letter about it was immediately sent to his old ally, White King. Frightened witnesses said that injuries on the King's body appeared from nothing. Axes began to move themselves and stroke King. After all, a strange force raised him up and threw down from a palace balcony mortally.
After White King had knew about it, he began to feel real danger. He understood that it's an awful deed of invisible Black-White King, who was considered dead after a legendary year, when Black and White King united to catch Black-White King, after what he was brutally hanged.
The danger seemed to be over, and Kings got back to their kingdoms and returned to their basic life. But now White King needs to defend his life without Black King. Fortunately, when Black King was still alive, he created a new chess piece, Guardian. This awful piece is always attacking all neighboring cells and a cell under itself, even if it's nothing (seen) in this cell (of course, that precautions were made special to defend from Black-White Kings, in case of their sudden appearance). It can't injure itself, but it kills all spirited, occupying the same or neighboring cell with this piece, including other Guardians. The cell is declared neighboring in the Chess World if it shares a common edge with the corresponding cell. It's well-known that retired Black King used these pieces to defend himself and his kingdom (a kingdom in the Chess World is a rectangle with M rows and N columns with some cells removed). For full protection, he had put Guardians in some cells of his kingdom, so that all cells were defended by at least one Guardian, and the number of Guardians used was minimal possible.
But, as a time had shown, it wasn't enough to protect Black King from an awful avenger. White King is now in horror. He realizes, that Black-White King had avoided punishment (it's not very amazing, because nobody had seen his corpse), and now, after killing Black King, he will want to kill White King too. So, really, this strange subject could be even another Black-White King, while nothing knows how they appear in the world (maybe except Black and White Kings. They can naturally know it, because they spent very much time together and shared the same secrets).
That's why White King urgently needs a new way of defending his kingdom, but while it's not developed yet, he wants to defend his kingdom maximally using Guardians. For this purpose he wants to put as many Guardians as possible. Of course, he understands that if he puts Guardians in every cell of his kingdom, they will kill each other immediately and the kingdom will become absolutely unsafe. As he feels a real danger, he is ready to do everything for the sake of kingdom's safety. You have a real chance to help White King to put maximal possible number of Guardians inside the kingdom, so that no one of them will kill another Guardian, and they will defend all the cells of the kingdom from invisible Black-White Kings and other genetic mutants.

Input
On the first line of input file there are two numbers M and N, (1<=N,M<=200). Then M lines of N numbers follow. I-th number in J-th line is 0 if respective cell in kingdom is removed or 1 in other case.

Output
On the first line of output file must be only one integer - maximal possible number of Guardians. Next M lines, N symbols each, represent the placement of K guardians in the kingdom. Symbol must be ".", if respective cell is empty, "G", if Guardian placed in it, or "#" if cell is removed from board. Note that you do not need to defend removed cells. If there are several solutions, output any one of them.

Sample test(s)

Input
3 5
1 1 1 0 0
1 0 0 0 1
1 1 0 1 1

Output
5
G.G##
.###G
G.#G.
Author:	Alexey Preobrajensky
Resource:	---
Date:	October, 2003

<|response|>
## 1. Abridged Problem Statement

You are given an `M × N` board, where some cells exist (`1`) and some are removed (`0`).

Place the maximum possible number of Guardians on existing cells such that:

1. No two Guardians are on edge-neighboring cells.
2. Every existing cell is defended, meaning it either contains a Guardian or shares an edge with a Guardian.

Output the maximum number of Guardians and one valid placement:

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

Constraints:

```text
1 ≤ M, N ≤ 200
```

---

## 2. Key Observations

### Observation 1: Model the board as a graph

Create a graph where:

- every existing cell is a vertex,
- two vertices are connected if their cells share an edge.

A Guardian attacks its own cell and its edge-neighboring cells.

Therefore:

- two Guardians cannot be adjacent,
- every vertex must be either chosen or adjacent to a chosen vertex.

So we need a set of vertices that is:

1. an **independent set** — no two chosen vertices are adjacent,
2. a **dominating set** — every vertex is chosen or adjacent to a chosen vertex.

We want the largest such set.

---

### Observation 2: A maximum independent set is automatically dominating

Suppose `S` is a maximum independent set.

If there exists a vertex `v` such that:

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

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

That contradicts the maximality of `S`.

Therefore:

```text
Any maximum independent set is also dominating.
```

So the problem becomes:

```text
Find a maximum independent set of the grid graph.
```

---

### Observation 3: The grid graph is bipartite

Color cells like a chessboard:

```text
(row + column) % 2 == 0 → left side
(row + column) % 2 == 1 → right side
```

Every edge connects cells of different parity, so the graph is bipartite.

---

### Observation 4: Use König’s theorem

For bipartite graphs:

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

By König’s theorem:

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

So:

1. Find a maximum matching using Hopcroft-Karp.
2. Recover a minimum vertex cover.
3. Take its complement to get a maximum independent set.

---

## 3. Full Solution Approach

### Step 1: Build the bipartite graph

For each existing cell:

- if `(i + j) % 2 == 0`, put it in the left part,
- otherwise put it in the right part.

For every existing even-parity cell, add edges to all existing neighboring odd-parity cells.

---

### Step 2: Run Hopcroft-Karp

Hopcroft-Karp finds a maximum matching in:

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

Here:

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

So this is efficient enough.

---

### Step 3: Recover minimum vertex cover

After finding a maximum matching:

1. Start BFS from all unmatched left vertices.
2. Traverse alternating paths:
   - from left to right using non-matching edges,
   - from right to left using matching edges.

Let:

- `visitedLeft` be visited left vertices,
- `visitedRight` be visited right vertices.

Then a minimum vertex cover is:

```text
(left vertices not visited) ∪ (right vertices visited)
```

---

### Step 4: Get maximum independent set

The maximum independent set is the complement of the minimum vertex cover:

```text
(left vertices visited) ∪ (right vertices not visited)
```

Place Guardians on exactly these cells.

---

### Complexity

Let `V` be the number of existing cells and `E` the number of neighboring pairs.

```text
Time:  O(E sqrt(V))
Memory: O(V + E)
```

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
    Hopcroft-Karp algorithm for maximum bipartite matching.

    Left side vertices:  0 ... leftSize - 1
    Right side vertices: 0 ... rightSize - 1

    adj[u] stores right-side neighbors of left vertex u.
*/
class HopcroftKarp {
public:
    int leftSize, rightSize;

    vector<vector<int>> adj;

    // pairU[u] = matched right vertex of left vertex u, or -1
    vector<int> pairU;

    // pairV[v] = matched left vertex of right vertex v, or -1
    vector<int> pairV;

    // BFS distance for left vertices
    vector<int> dist;

    HopcroftKarp(int L, int R) {
        leftSize = L;
        rightSize = R;

        adj.assign(leftSize, {});
        pairU.assign(leftSize, -1);
        pairV.assign(rightSize, -1);
        dist.assign(leftSize, -1);
    }

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

    /*
        BFS builds layers of alternating paths.

        It starts from all unmatched left vertices.

        Returns true if there exists at least one augmenting path.
    */
    bool bfs() {
        queue<int> q;

        for (int u = 0; u < leftSize; u++) {
            if (pairU[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = -1;
            }
        }

        bool foundAugmentingPath = false;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : adj[u]) {
                int matchedLeft = pairV[v];

                if (matchedLeft == -1) {
                    // We can reach an unmatched right vertex,
                    // so an augmenting path exists.
                    foundAugmentingPath = true;
                } else if (dist[matchedLeft] == -1) {
                    // Continue through the matching edge
                    // from right vertex v to its matched left vertex.
                    dist[matchedLeft] = dist[u] + 1;
                    q.push(matchedLeft);
                }
            }
        }

        return foundAugmentingPath;
    }

    /*
        DFS tries to find an augmenting path starting from left vertex u,
        respecting the BFS layering.
    */
    bool dfs(int u) {
        for (int v : adj[u]) {
            int matchedLeft = pairV[v];

            if (
                matchedLeft == -1 ||
                (dist[matchedLeft] == dist[u] + 1 && dfs(matchedLeft))
            ) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }

        // Mark as useless in this BFS phase.
        dist[u] = -1;
        return false;
    }

    int maximumMatching() {
        int matchingSize = 0;

        while (bfs()) {
            for (int u = 0; u < leftSize; u++) {
                if (pairU[u] == -1 && dfs(u)) {
                    matchingSize++;
                }
            }
        }

        return matchingSize;
    }
};

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

    int M, N;
    cin >> M >> N;

    vector<vector<int>> grid(M, vector<int>(N));

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
        }
    }

    /*
        id[i][j] stores the ID of cell (i, j)
        inside its corresponding bipartite side.
    */
    vector<vector<int>> id(M, vector<int>(N, -1));

    int leftCount = 0;
    int rightCount = 0;

    /*
        Assign IDs to existing cells according to checkerboard parity.
    */
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                if ((i + j) % 2 == 0) {
                    id[i][j] = leftCount++;
                } else {
                    id[i][j] = rightCount++;
                }
            }
        }
    }

    HopcroftKarp hk(leftCount, rightCount);

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

    /*
        Build edges from even-parity cells to neighboring odd-parity cells.
    */
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1 && (i + j) % 2 == 0) {
                int u = id[i][j];

                for (int d = 0; d < 4; d++) {
                    int ni = i + di[d];
                    int nj = j + dj[d];

                    if (
                        ni >= 0 && ni < M &&
                        nj >= 0 && nj < N &&
                        grid[ni][nj] == 1
                    ) {
                        int v = id[ni][nj];
                        hk.addEdge(u, v);
                    }
                }
            }
        }
    }

    /*
        Step 1: Find maximum matching.
    */
    hk.maximumMatching();

    /*
        Step 2: Find vertices reachable by alternating paths
        from unmatched left vertices.

        From left to right: use only non-matching edges.
        From right to left: use only matching edges.
    */
    vector<char> visitedLeft(leftCount, false);
    vector<char> visitedRight(rightCount, false);

    queue<int> q;

    for (int u = 0; u < leftCount; u++) {
        if (hk.pairU[u] == -1) {
            visitedLeft[u] = true;
            q.push(u);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : hk.adj[u]) {
            // From left to right, we only traverse non-matching edges.
            if (hk.pairU[u] == v) {
                continue;
            }

            if (!visitedRight[v]) {
                visitedRight[v] = true;

                // From right to left, traverse the matching edge if it exists.
                int matchedLeft = hk.pairV[v];

                if (matchedLeft != -1 && !visitedLeft[matchedLeft]) {
                    visitedLeft[matchedLeft] = true;
                    q.push(matchedLeft);
                }
            }
        }
    }

    /*
        Minimum vertex cover:
            left not visited + right visited

        Maximum independent set, its complement:
            left visited + right not visited
    */
    vector<char> chosenLeft(leftCount, false);
    vector<char> chosenRight(rightCount, false);

    for (int u = 0; u < leftCount; u++) {
        if (visitedLeft[u]) {
            chosenLeft[u] = true;
        }
    }

    for (int v = 0; v < rightCount; v++) {
        if (!visitedRight[v]) {
            chosenRight[v] = true;
        }
    }

    /*
        Construct answer board.
    */
    vector<string> answer(M, string(N, '#'));

    int guardianCount = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 0) {
                answer[i][j] = '#';
            } else {
                bool chosen;

                if ((i + j) % 2 == 0) {
                    chosen = chosenLeft[id[i][j]];
                } else {
                    chosen = chosenRight[id[i][j]];
                }

                if (chosen) {
                    answer[i][j] = 'G';
                    guardianCount++;
                } else {
                    answer[i][j] = '.';
                }
            }
        }
    }

    cout << guardianCount << '\n';

    for (int i = 0; i < M; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys
from collections import deque


def hopcroft_karp(adj, left_size, right_size):
    """
    Hopcroft-Karp maximum bipartite matching.

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

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

    pair_u = [-1] * left_size
    pair_v = [-1] * right_size
    dist = [-1] * left_size

    def bfs():
        """
        Builds BFS layers from all unmatched left vertices.

        Returns True if an augmenting path may exist.
        """

        q = deque()

        for u in range(left_size):
            if pair_u[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = -1

        found_augmenting_path = False

        while q:
            u = q.popleft()

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

                if matched_left == -1:
                    # We reached an unmatched right vertex.
                    found_augmenting_path = True
                elif dist[matched_left] == -1:
                    # Continue along the alternating path.
                    dist[matched_left] = dist[u] + 1
                    q.append(matched_left)

        return found_augmenting_path

    def dfs(u):
        """
        Tries to find an augmenting path starting from left vertex u.
        """

        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 this vertex as unusable in this BFS 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):
    """
    Computes maximum independent set in a bipartite graph
    using König's theorem.

    First recover minimum vertex cover:

        minimum vertex cover =
            left vertices not visited by alternating BFS
            +
            right vertices visited by alternating BFS

    Therefore, maximum independent set is:

        left vertices visited
        +
        right vertices not visited
    """

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

    q = deque()

    # Start alternating BFS 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()

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

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

                # From right to left, traverse only the matching edge.
                matched_left = pair_v[v]

                if matched_left != -1 and not visited_left[matched_left]:
                    visited_left[matched_left] = True
                    q.append(matched_left)

    chosen_left = [False] * left_size
    chosen_right = [False] * right_size

    # Maximum independent set:
    # left visited + right not visited.
    for u in range(left_size):
        if visited_left[u]:
            chosen_left[u] = True

    for v in range(right_size):
        if not visited_right[v]:
            chosen_right[v] = True

    return chosen_left, chosen_right


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

    if not data:
        return

    it = iter(data)

    M = int(next(it))
    N = int(next(it))

    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 vertex ID of cell (i, j)
    inside its bipartite side.
    """
    id_cell = [[-1] * N for _ in range(M)]

    left_count = 0
    right_count = 0

    # Assign IDs 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

    # Build adjacency list from left side to right side.
    adj = [[] for _ in range(left_count)]

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

    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)

    # DFS recursion can be deep.
    sys.setrecursionlimit(1_000_000)

    # Step 1: maximum matching.
    pair_u, pair_v = hopcroft_karp(adj, left_count, right_count)

    # Step 2: maximum independent set.
    chosen_left, chosen_right = maximum_independent_set(
        adj,
        pair_u,
        pair_v,
        left_count,
        right_count
    )

    # Build output board.
    answer = [['#'] * N for _ in range(M)]

    guardian_count = 0

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

                if chosen:
                    answer[i][j] = 'G'
                    guardian_count += 1
                else:
                    answer[i][j] = '.'

    output = [str(guardian_count)]

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

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


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