<|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.

334. Tiny Puzzle
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You've decided to make a puzzle as a part of the "re-branding" campaign run by your company. In the box this puzzle will look as the new logo of your company, that is, it will be a set of 9 (nine) connected unit squares on a rectangular grid. However, these 9 squares will not necessarily all be glued together, i.e., they may form several connected parts (however, you're not allowed to split squares in the middle). The objective of the puzzle will be to rearrange those parts so that they form a 3x3 square. When rearranging, one is only allowed to shift parts, and NOT to rotate or to flip them.

To make the puzzle more challenging, you need to have as few parts as possible. Given the logo, compute how many parts do you need and how to rearrange them into a 3x3 square.

Every word "connected" in the problem statement means connectedness in the side-by-side sense.

Input
The first line of input contains two integers H and W. The next H lines will contain W characters each, describing your logo. Each of those characters will be either '.' (dot), denoting an empty square, or 'X' (capital English letter X), denoting a square occupied by the logo. All the 'X's will form a connected figure, there will be exactly 9 'X's in input. The first line, the last line, the first column and the last column will contain at least one 'X', in other words, there will not be unnecessary empty rows at any side of the grid.

Output
On the first line, output the required number of parts K. Afterwards, output one of the possible rearrangements, more precisely: on the next H lines output the logo with all the 'X's replaced by the first K capital letters of English alphabet, each letter denoting one part. Then output an empty line, and then 3 lines containing 3 characters each, containing the same K parts but shifted around so that they form a 3x3 square.

All the parts must be connected, and K must be as little as possible. If there're several possible solutions, output any.

Example(s)
sample input
sample output
4 5
....X
....X
..XXX
XXXX.
3
....A
....C
..CCC
BBCC.
 
BBC
CCC
CCA

<|response|>
## 1) Abridged problem statement (concise)

You are given an \(H \times W\) grid containing exactly **9** cells marked `X`. These 9 cells form a single 4-neighbor connected figure.

You may **cut** this figure into \(K\) **connected parts** (each part must be 4-neighbor connected in the original grid). Then you may **shift (translate)** each part (no rotation, no flip) so that all 9 cells exactly form a **filled 3×3 square**.

Find the **minimum** possible \(K\), and output:
1) \(K\)  
2) the original grid with each `X` replaced by a letter `A..` indicating its part  
3) a blank line  
4) a 3×3 grid showing the same letters arranged into a full 3×3 square via shifts.

Any optimal solution is accepted.

---

## 2) Key observations

1. **Only 9 cells exist.**  
   The target (3×3) also contains 9 cells, so we are looking for a **bijection** from the 9 input cells to the 9 positions of a 3×3 square.

2. **Brute force over all bijections is feasible.**  
   There are \(9! = 362{,}880\) permutations—small enough.

3. **Translation vectors determine which cells can be in the same part.**  
   If an input cell at \((r,c)\) is mapped to target \((R,C)\), it must move by  
   \[
   (\Delta r, \Delta c) = (R-r,\, C-c)
   \]
   A whole part moves rigidly, so **all cells of a part must share the same \((\Delta r,\Delta c)\)**.

4. **Parts must be connected in the original logo.**  
   Even if multiple cells share the same translation, they may still form multiple connected components in the original grid—each component is a separate part.

5. **So for a fixed permutation:**  
   - Compute \((\Delta r,\Delta c)\) for each of the 9 cells.
   - In the original adjacency graph (4-neighbor among the 9 cells), union adjacent cells **only if** they share the same \((\Delta r,\Delta c)\).
   - The number of DSU components equals the number of parts needed for that permutation.

We choose the permutation minimizing this count.

---

## 3) Full solution approach

### Step A: Parse input and index the 9 `X` cells
Store their coordinates in an array `cells[0..8]`.

### Step B: Build adjacency among these 9 cells
Create a graph where `i` is connected to `j` if their coordinates differ by Manhattan distance 1 (side-adjacent).

### Step C: Try all permutations of mapping to 3×3 positions
Number target positions 0..8, where:
- target row = `pos / 3`
- target col = `pos % 3`

For each permutation `p`:
- `p[i]` is the target position assigned to input cell `i`.

Compute translations:
- `dr[i] = (p[i]/3) - cells[i].r`
- `dc[i] = (p[i]%3) - cells[i].c`

Build DSU:
- For each original adjacency edge (i,j), if `dr[i]==dr[j] && dc[i]==dc[j]`, union(i,j).

Count DSU roots among 0..8 ⇒ `parts(p)`.

Track permutation with minimal parts.

### Step D: Construct output for the best permutation
- Rebuild DSU for best permutation.
- Assign letters `A..` to DSU components.
- Print:
  - `K`
  - original grid: each `X` replaced by component letter
  - blank line
  - 3×3 grid: place each cell’s letter into its assigned target position.

Complexity: \(9! \times O(1)\) small constant work ⇒ easily fast enough.

---

## 4) C++ implementation (detailed comments)

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

// ---------------- DSU (Disjoint Set Union / Union-Find) ----------------
struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) { init(n); }

    void init(int n) {
        p.resize(n);
        sz.assign(n, 1);
        iota(p.begin(), p.end(), 0);
    }

    int root(int x) {
        if (p[x] == x) return x;
        return p[x] = root(p[x]);
    }

    void unite(int a, int b) {
        a = root(a), b = root(b);
        if (a == b) return;
        if (sz[a] > sz[b]) swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
    }
};

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

    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) cin >> grid[i];

    // Collect coordinates of the 9 occupied cells
    vector<pair<int,int>> cells;
    for (int r = 0; r < H; r++) {
        for (int c = 0; c < W; c++) {
            if (grid[r][c] == 'X') cells.push_back({r, c});
        }
    }

    // Build adjacency list among these 9 cells (4-neighbor adjacency)
    vector<vector<int>> adj(9);
    for (int i = 0; i < 9; i++) {
        for (int j = i + 1; j < 9; j++) {
            int d = abs(cells[i].first - cells[j].first)
                  + abs(cells[i].second - cells[j].second);
            if (d == 1) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // Helper: for a given permutation p (mapping cell i -> target position p[i]),
    // build DSU components of parts:
    // union adjacent cells iff they share the same translation vector (dr, dc).
    auto build_dsu = [&](const array<int,9>& p) -> DSU {
        DSU dsu(9);
        int dr[9], dc[9];

        for (int i = 0; i < 9; i++) {
            int tr = p[i] / 3;  // target row in 3x3
            int tc = p[i] % 3;  // target col in 3x3
            dr[i] = tr - cells[i].first;
            dc[i] = tc - cells[i].second;
        }

        for (int i = 0; i < 9; i++) {
            for (int j : adj[i]) {
                if (j > i && dr[i] == dr[j] && dc[i] == dc[j]) {
                    dsu.unite(i, j);
                }
            }
        }
        return dsu;
    };

    // Iterate all 9! permutations
    array<int,9> perm;
    iota(perm.begin(), perm.end(), 0);

    int bestK = 10;
    array<int,9> bestP{};

    do {
        DSU dsu = build_dsu(perm);

        // Count DSU components (roots) among 0..8
        int cnt = 0;
        for (int i = 0; i < 9; i++) {
            if (dsu.root(i) == i) cnt++;
        }

        if (cnt < bestK) {
            bestK = cnt;
            bestP = perm;
            if (bestK == 1) break; // cannot do better
        }
    } while (next_permutation(perm.begin(), perm.end()));

    // Rebuild DSU for best permutation and assign component labels 0..K-1
    DSU bestDsu = build_dsu(bestP);

    vector<int> rootLabel(9, -1);
    int cur = 0;
    for (int i = 0; i < 9; i++) {
        int r = bestDsu.root(i);
        if (rootLabel[r] == -1) rootLabel[r] = cur++;
    }

    // Output K
    cout << bestK << "\n";

    // Output labeled original grid
    vector<string> outGrid = grid;
    for (int i = 0; i < 9; i++) {
        auto [r, c] = cells[i];
        int lab = rootLabel[bestDsu.root(i)];
        outGrid[r][c] = char('A' + lab);
    }
    for (auto &row : outGrid) cout << row << "\n";

    cout << "\n"; // blank line required

    // Output labeled 3x3 arrangement
    vector<string> small(3, string(3, '.'));
    for (int i = 0; i < 9; i++) {
        int pos = bestP[i];
        int tr = pos / 3, tc = pos % 3;
        int lab = rootLabel[bestDsu.root(i)];
        small[tr][tc] = char('A' + lab);
    }
    for (auto &row : small) cout << row << "\n";

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from itertools import permutations

# ---------------- DSU (Union-Find) ----------------
class DSU:
    def __init__(self, n: int):
        self.par = list(range(n))
        self.sz = [1] * n

    def root(self, x: int) -> int:
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x

    def unite(self, a: int, b: int) -> None:
        a, b = self.root(a), self.root(b)
        if a == b:
            return
        if self.sz[a] > self.sz[b]:
            a, b = b, a
        self.par[a] = b
        self.sz[b] += self.sz[a]


def solve() -> None:
    data = sys.stdin.read().splitlines()
    H, W = map(int, data[0].split())
    grid = data[1:1 + H]

    # Collect coordinates of the 9 'X' cells
    cells = []
    for r in range(H):
        for c in range(W):
            if grid[r][c] == 'X':
                cells.append((r, c))

    # Build adjacency among the 9 cells (4-neighbor)
    adj = [[] for _ in range(9)]
    for i in range(9):
        r1, c1 = cells[i]
        for j in range(i + 1, 9):
            r2, c2 = cells[j]
            if abs(r1 - r2) + abs(c1 - c2) == 1:
                adj[i].append(j)
                adj[j].append(i)

    # For a permutation p: cell i -> target position p[i] in 0..8,
    # build DSU components representing parts.
    def build_dsu(p):
        dsu = DSU(9)
        dr = [0] * 9
        dc = [0] * 9

        # translation needed for each cell
        for i in range(9):
            tr, tc = divmod(p[i], 3)   # target coords in 3x3
            r, c = cells[i]            # original coords
            dr[i] = tr - r
            dc[i] = tc - c

        # union adjacent original cells if they share the same translation
        for i in range(9):
            for j in adj[i]:
                if j > i and dr[i] == dr[j] and dc[i] == dc[j]:
                    dsu.unite(i, j)
        return dsu

    bestK = 10
    bestP = None

    # Try all 9! bijections
    for p in permutations(range(9)):
        dsu = build_dsu(p)
        parts = len({dsu.root(i) for i in range(9)})
        if parts < bestK:
            bestK = parts
            bestP = p
            if bestK == 1:
                break

    # Rebuild DSU for best permutation and assign letters
    dsu = build_dsu(bestP)
    root_to_label = {}
    next_label = 0
    for i in range(9):
        r = dsu.root(i)
        if r not in root_to_label:
            root_to_label[r] = next_label
            next_label += 1

    out = []
    out.append(str(bestK))

    # Labeled original grid
    g2 = [list(row) for row in grid]
    for i in range(9):
        r, c = cells[i]
        lab = root_to_label[dsu.root(i)]
        g2[r][c] = chr(ord('A') + lab)
    out.extend("".join(row) for row in g2)

    out.append("")  # blank line

    # Labeled 3x3 arrangement
    small = [["."] * 3 for _ in range(3)]
    for i in range(9):
        tr, tc = divmod(bestP[i], 3)
        lab = root_to_label[dsu.root(i)]
        small[tr][tc] = chr(ord('A') + lab)
    out.extend("".join(row) for row in small)

    sys.stdout.write("\n".join(out))


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

If you want, I can also add a short section on **why DSU components correspond exactly to parts**, or show how to reduce constant factors further (though this already fits easily in the limits).