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

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.

Choose the permutation minimizing this count.

---

## 3. Full solution approach

- Collect the 9 `X` cells; precompute their 4-neighbor adjacency.
- Enumerate all \(9!\) permutations of target positions using `next_permutation`.
- For each permutation, call `build_dsu`: compute translations, union adjacent cells sharing the same translation, count DSU components.
- Track the best (minimum components) permutation.
- Rebuild DSU for the best permutation, assign letters A, B, ... to components, print labeled original grid and the labeled 3×3 target.

---

## 4. C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/dsu.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 DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n, m;
vector<string> tbl;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    cin >> tbl;
}

void solve() {
    // The main observation to make is that there are exactly 9 cells that are
    // an X, and 9! = 362880 is actually fairly small. This means we can try all
    // possible mappings to the 3x3 grid. Afterwards, we simply want to figure
    // out what's the least number of letters, such that the compositions would
    // be connected in both the original table and have the same "shapes". For a
    // given mapping, each cell has a delta (the shift from its original
    // position to its 3x3 position). Cells in the same part must share the same
    // delta (since parts are only shifted, not rotated). So we group cells by
    // delta, and within each group it's enough to count the connected
    // components (say using a DSU). The total number of components across
    // all groups is the number of parts for that permutation. We take the
    // minimum over all 9! permutations, where the total number of operations
    // will just be a few million and would fit in the constraints very
    // comfortably.

    vector<pair<int, int>> cells;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(tbl[i][j] == 'X') {
                cells.push_back({i, j});
            }
        }
    }

    vector<vector<int>> adj(9);
    for(int i = 0; i < 9; i++) {
        for(int j = i + 1; j < 9; j++) {
            if(abs(cells[i].first - cells[j].first) +
                   abs(cells[i].second - cells[j].second) ==
               1) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    auto build_dsu = [&](const vector<int>& p) {
        DSU dsu(9);
        vector<int> dr(9), dc(9);
        for(int i = 0; i < 9; i++) {
            dr[i] = p[i] / 3 - cells[i].first;
            dc[i] = p[i] % 3 - 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;
    };

    vector<int> perm(9);
    iota(perm.begin(), perm.end(), 0);

    int best_parts = 10;
    vector<int> best_perm;

    do {
        auto dsu = build_dsu(perm);

        int cnt = 0;
        for(int i = 0; i < 9; i++) {
            if(dsu.root(i) == i) {
                cnt++;
            }
        }

        if(cnt < best_parts) {
            best_parts = cnt;
            best_perm = perm;
            if(best_parts == 1) {
                break;
            }
        }
    } while(next_permutation(perm.begin(), perm.end()));

    auto dsu = build_dsu(best_perm);

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

    cout << best_parts << "\n";
    auto grid = tbl;
    for(int i = 0; i < 9; i++) {
        grid[cells[i].first][cells[i].second] = 'A' + label[dsu.root(i)];
    }
    for(auto& row: grid) {
        cout << row << "\n";
    }
    cout << "\n";

    vector<string> small(3, string(3, '.'));
    for(int i = 0; i < 9; i++) {
        small[best_perm[i] / 3][best_perm[i] % 3] = 'A' + label[dsu.root(i)];
    }
    for(auto& row: small) {
        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;
}
```

---

## 5. Python Solution

```python
import sys
from itertools import permutations

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

    def root(self, x: int) -> int:
        # Path compression
        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
        # Union by size: attach smaller to larger
        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().strip().splitlines()
    h, w = map(int, data[0].split())
    grid = data[1:1+h]

    # Collect the 9 occupied cells
    cells = []
    for r in range(h):
        for c in range(w):
            if grid[r][c] == 'X':
                cells.append((r, c))

    # Build adjacency list among the 9 cells in the original figure
    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)

    # Build DSU for a given mapping p[i] = target position (0..8) for input cell i
    def build_dsu(p):
        dsu = DSU(9)

        # Translation vectors needed for each cell i
        dr = [0] * 9
        dc = [0] * 9
        for i in range(9):
            tr, tc = divmod(p[i], 3)   # target row/col in 3x3
            r, c = cells[i]            # original position
            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

    best_parts = 10
    best_perm = None

    # Try all 9! bijections from input cells to 3x3 target positions
    for p in permutations(range(9)):
        dsu = build_dsu(p)

        # Count components (roots)
        roots = set(dsu.root(i) for i in range(9))
        parts = len(roots)

        if parts < best_parts:
            best_parts = parts
            best_perm = p
            if best_parts == 1:
                break

    # Rebuild DSU for best permutation and assign letters to components
    dsu = build_dsu(best_perm)

    # Map DSU root -> label index 0..K-1
    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

    # Output K
    out = []
    out.append(str(best_parts))

    # Print original grid with X replaced by letters
    grid2 = [list(row) for row in grid]
    for i in range(9):
        r, c = cells[i]
        lab = root_to_label[dsu.root(i)]
        grid2[r][c] = chr(ord('A') + lab)
    out.extend("".join(row) for row in grid2)

    # Blank line
    out.append("")

    # Print 3x3 target arrangement
    small = [["."] * 3 for _ in range(3)]
    for i in range(9):
        tr, tc = divmod(best_perm[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()
```
