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

399. Berodoskar Development
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

Not far away from Berland there is a small stony isle in the ocean. The name of the isle is Berodoskar and it is an ideal place for a military base. The only problem is lack of fresh water, but such a negligible problem will never stop Berl III, the King of Berland. He has stated that there would be exactly two water-storage reservoirs with desalinated water. The best way to organize reservoirs is to use existing craters located on the isle and connect them with the ocean by a water-pipe. And you are the person responsible for the water-storage system creation. You have a map of Berodoskar on which the isle is represented as a rectangle divided into unit squares by horizontal and vertical lines. Each unit square is marked with either 'X' character if it contains a part of crater or with '.' character if there is no crater on this square. If two squares marked with 'X' have the common edge they are considered as parts of one crater. There are no squares marked with 'X' connected with the ocean. The whole area around the square is the ocean. The water-pipe you are to create should connect any two of craters with the ocean. It is allowed to connect more than two craters, but at least two craters should be connected. The water-pipe will consist of segments connected by edge and each segment will occupy the whole non-crater unit square. A pipe is connected with a crater if they have a common edge. You want to minimize number of squares involved into water-storage system creation. It is possible that two independent water-pipes are more efficient than one branched (see examples).
Input
The first line contains two integer numbers N and M — number of unit squares in vertical and horizontal directions (3 <= N, M <= 15). After that N lines follow describing the isle. Each line contains exactly M characters 'X' or '.'. It is guaranteed that there are at least two craters reachable from the ocean.
Output
Output N lines with M characters in each — an isle map is in the same format as in the input, but with the water-pipe indicated. Squares with the water-pipe should be marked with '*' instead of '.'. If there are several solutions with the same minimal number of squares used, output any one of them.
Example(s)
sample input
sample output
5 7
.......
.......
..X....
.....X.
.......
.......
.......
**X....
.....X*
.......

sample input
sample output
10 13
.............
.............
..XXXXX......
..X..X.......
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............
........*....
........*....
..XXXXX**....
..X..X..*....
..X.X.X.X....
..X...X......
..XXXXX......
.............
.............
.............

<|response|>
## 1. Abridged problem statement

You are given an N x M grid (3 <= N, M <= 15) of:

- `X` = crater cell,
- `.` = normal land cell where pipes may be built.

4-adjacent `X` cells form a single crater. The ocean is outside the rectangle, so any `.` cell on the border can connect to the ocean, but no `X` cell touches the ocean.

Build pipes by changing some `.` cells into `*`. Pipes are 4-connected and a pipe is connected to a crater if a pipe cell shares an edge with any `X` cell of that crater.

Goal: choose a set of `.` cells to mark `*` so that at least two distinct craters become connected to the ocean (via pipes), minimizing the number of `*` cells. Output any optimal resulting grid.

---

## 2. Key observations

1. **Grid is tiny** (max 15 x 15 = 225 cells), so we can run many BFS computations cheaply.
2. Pipes can only occupy `.` cells; `X` cells are blocked.
3. For each crater, pipes connect to it via adjacent `.` cells (its **ports**). Ocean ports are border `.` cells.
4. Any optimal solution falls into one of two shapes:
   - **(A) Two independent pipes**: one from crater A to ocean, one from crater B to ocean. Their pipe-cell union is the cost.
   - **(B) One connected branched network** touching the ocean and at least two craters. For 3 terminals in an unweighted graph, the optimal Steiner tree has **three shortest paths meeting at one cell** (the meeting point).
5. Enumerating pairs of craters (there are only two, but the code handles K >= 2) and all possible meeting cells is sufficient.

---

## 3. Full solution approach

**Step 1 - Label craters.** Flood-fill (BFS) over `X` cells; assign `crater_id[r][c]` in [0..K-1].

**Step 2 - Collect ports.** For each `.` cell, check 4-neighbors; if a neighbor is `X`, this `.` is a port of that crater. Ocean sources = all border `.` cells.

**Step 3 - BFS distances.**
- Multi-source BFS from ocean sources (start distance 1): `dist_o[r][c]` = min pipe cells to connect (r,c) to the ocean. Store parent pointers `par_o`.
- For each crater k, multi-source BFS from its ports: `dist_c[k][r][c]`.

**Step 4 - Candidate (A).** For each crater k, `cost[k] = min over ports p of dist_o[p]`. Sort craters by cost, take the two cheapest. Reconstruct both ocean paths via `par_o`, take the union set for the true cost.

**Step 5 - Candidate (B).** Enumerate crater pair i < j and meeting cell m (must be `.`). If all three distances are finite, the union estimate is:

```
dist_o[m] + (dist_c[i][m] - 1) + (dist_c[j][m] - 1)
```

(The -1's account for m being shared.) Keep the minimum. Reconstruct:
- Ocean path: trace `par_o` from m.
- Paths to crater ports: BFS from m (distance 0), trace best ports via parents from m.
- Union all three paths.

**Step 6 - Output.** Pick the smaller of the two candidates' actual union sets, mark those cells `*`, print the grid.

Complexity: O(K^2 * N * M), trivial for 225 cells.

---

## 4. C++ implementation

```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;
vector<string> grid;

void read() {
    cin >> N >> M;
    grid.assign(N, "");
    for(int i = 0; i < N; i++) {
        cin >> grid[i];
    }
}

void solve() {
    // The grid is tiny (N, M <= 15), so we can afford to enumerate "where
    // pipes meet" directly. It's very important to note that there are only two
    // craters which is mentioned in the problem statement. A pipe set is a
    // collection of '.' cells; any optimal solution falls into one of two
    // shapes:
    //
    //     (a) two independent paths, each connecting one crater to the ocean;
    //     (b) a single connected '*' component that touches the ocean and
    //         at least two craters (the Steiner / branched shape).
    //
    // We label craters by 4-connected flood fill of the 'X' cells, and for
    // each crater i collect its ports = the '.' cells edge-adjacent to it.
    // Every '.' cell on the border is an ocean port (the area around the isle
    // is ocean). Then we run two flavors of multi-source BFS over '.' cells:
    //
    //     distO[r][c]   = min cells from (r,c) to any ocean port (1 at the
    //                     port itself, +1 per step), with parent pointers;
    //     distC[i][r][c] = same thing but sourced from crater i's ports.
    //
    // For shape (a), the cheapest single-crater connection has cost
    // cost[i] = min over ports p of crater i of distO[p]; pick the two
    // craters with the smallest cost[], reconstruct each path via parentO,
    // and take the union (the two paths may share cells, so we count by set
    // union, not sum).
    //
    // For shape (b), the optimal Steiner tree on three terminals (ocean +
    // two craters) in an unweighted graph is always realized by three
    // shortest paths meeting at a single vertex m. Iterate over every pair
    // i < j of craters and every candidate meeting cell m; the union of the
    // three paths uses
    //
    //     distO[m] + (distC[i][m] - 1) + (distC[j][m] - 1)
    //
    // cells (the -1's account for m being shared). Covering >= 3 craters
    // with one component cannot beat the best pair, so enumerating pairs is
    // enough.
    //
    // Compare the two candidates' actual cell counts -- for shape (b) we do
    // one extra BFS from the chosen m to recover the in-tree paths to the
    // best port of crater i and crater j, then union with the ocean path --
    // mark those cells with '*', and print the grid. Total time is
    // O(K^2 * N * M), trivially within limits.

    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
    const int INF = INT_MAX;

    auto in_bounds = [&](int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    };

    vector<vector<int>> crater_id(N, vector<int>(M, -1));
    int K = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(grid[i][j] != 'X' || crater_id[i][j] != -1) {
                continue;
            }
            queue<pair<int, int>> q;
            q.push({i, j});
            crater_id[i][j] = K;
            while(!q.empty()) {
                auto [r, c] = q.front();
                q.pop();
                for(int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if(in_bounds(nr, nc) && grid[nr][nc] == 'X' &&
                       crater_id[nr][nc] == -1) {
                        crater_id[nr][nc] = K;
                        q.push({nr, nc});
                    }
                }
            }
            K++;
        }
    }

    vector<vector<pair<int, int>>> ports(K);
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(grid[i][j] != '.') {
                continue;
            }
            set<int> seen;
            for(int d = 0; d < 4; d++) {
                int ni = i + dr[d], nj = j + dc[d];
                if(in_bounds(ni, nj) && grid[ni][nj] == 'X') {
                    int cid = crater_id[ni][nj];
                    if(seen.insert(cid).second) {
                        ports[cid].push_back({i, j});
                    }
                }
            }
        }
    }

    auto bfs = [&](const vector<pair<int, int>>& sources, int start_dist) {
        vector<vector<int>> dist(N, vector<int>(M, INF));
        vector<vector<pair<int, int>>> par(
            N, vector<pair<int, int>>(M, {-1, -1})
        );
        queue<pair<int, int>> q;
        for(auto [r, c]: sources) {
            if(dist[r][c] == INF) {
                dist[r][c] = start_dist;
                q.push({r, c});
            }
        }
        while(!q.empty()) {
            auto [r, c] = q.front();
            q.pop();
            for(int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if(in_bounds(nr, nc) && grid[nr][nc] == '.' &&
                   dist[nr][nc] == INF) {
                    dist[nr][nc] = dist[r][c] + 1;
                    par[nr][nc] = {r, c};
                    q.push({nr, nc});
                }
            }
        }
        return make_pair(dist, par);
    };

    vector<pair<int, int>> ocean_sources;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(grid[i][j] == '.' &&
               (i == 0 || i == N - 1 || j == 0 || j == M - 1)) {
                ocean_sources.push_back({i, j});
            }
        }
    }
    auto [dist_o, par_o] = bfs(ocean_sources, 1);

    vector<vector<vector<int>>> dist_c(K);
    for(int k = 0; k < K; k++) {
        dist_c[k] = bfs(ports[k], 1).first;
    }

    auto best_port = [&](int k, const vector<vector<int>>& d) {
        pair<int, int> best = {-1, -1};
        int bd = INF;
        for(auto [r, c]: ports[k]) {
            if(d[r][c] < bd) {
                bd = d[r][c];
                best = {r, c};
            }
        }
        return best;
    };

    auto trace_path = [&](pair<int, int> start,
                          const vector<vector<pair<int, int>>>& par) {
        set<pair<int, int>> path;
        auto cur = start;
        while(cur.first != -1) {
            path.insert(cur);
            cur = par[cur.first][cur.second];
        }
        return path;
    };

    vector<int> cost(K, INF);
    for(int k = 0; k < K; k++) {
        for(auto [r, c]: ports[k]) {
            cost[k] = min(cost[k], dist_o[r][c]);
        }
    }
    vector<int> order(K);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return cost[a] < cost[b];
    });

    set<pair<int, int>> S_sep;
    int cost_sep = INF;
    if(K >= 2 && cost[order[0]] != INF && cost[order[1]] != INF) {
        auto pa = best_port(order[0], dist_o);
        auto pb = best_port(order[1], dist_o);
        auto sa = trace_path(pa, par_o);
        auto sb = trace_path(pb, par_o);
        S_sep.insert(sa.begin(), sa.end());
        S_sep.insert(sb.begin(), sb.end());
        cost_sep = (int)S_sep.size();
    }

    int min_multi = INF;
    int best_i = -1, best_j = -1;
    pair<int, int> best_m = {-1, -1};
    for(int i = 0; i < K; i++) {
        for(int j = i + 1; j < K; j++) {
            for(int r = 0; r < N; r++) {
                for(int c = 0; c < M; c++) {
                    if(grid[r][c] != '.') {
                        continue;
                    }
                    if(dist_o[r][c] == INF || dist_c[i][r][c] == INF ||
                       dist_c[j][r][c] == INF) {
                        continue;
                    }
                    int v = dist_o[r][c] + dist_c[i][r][c] - 1 +
                            dist_c[j][r][c] - 1;
                    if(v < min_multi) {
                        min_multi = v;
                        best_i = i;
                        best_j = j;
                        best_m = {r, c};
                    }
                }
            }
        }
    }

    set<pair<int, int>> S_multi;
    int cost_multi = INF;
    if(best_i != -1) {
        auto ocean_path = trace_path(best_m, par_o);
        auto [dist_m, par_m] = bfs({best_m}, 0);
        auto pi = best_port(best_i, dist_m);
        auto pj = best_port(best_j, dist_m);
        auto path_i = trace_path(pi, par_m);
        auto path_j = trace_path(pj, par_m);
        S_multi.insert(ocean_path.begin(), ocean_path.end());
        S_multi.insert(path_i.begin(), path_i.end());
        S_multi.insert(path_j.begin(), path_j.end());
        cost_multi = (int)S_multi.size();
    }

    set<pair<int, int>>& chosen = (cost_sep <= cost_multi) ? S_sep : S_multi;
    for(auto [r, c]: chosen) {
        grid[r][c] = '*';
    }
    for(auto& row: grid) {
        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 implementation (detailed comments)

```python
from collections import deque
import sys

INF = 10**9

def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    grid = [list(next(it).strip()) for _ in range(N)]

    # 4-neighborhood directions
    DR = (-1, 1, 0, 0)
    DC = (0, 0, -1, 1)

    def in_bounds(r: int, c: int) -> bool:
        return 0 <= r < N and 0 <= c < M

    # 1) Label crater components (connected components of 'X')
    crater_id = [[-1] * M for _ in range(N)]
    K = 0
    for i in range(N):
        for j in range(M):
            if grid[i][j] != 'X' or crater_id[i][j] != -1:
                continue
            q = deque([(i, j)])
            crater_id[i][j] = K
            while q:
                r, c = q.popleft()
                for d in range(4):
                    nr, nc = r + DR[d], c + DC[d]
                    if in_bounds(nr, nc) and grid[nr][nc] == 'X' and crater_id[nr][nc] == -1:
                        crater_id[nr][nc] = K
                        q.append((nr, nc))
            K += 1

    # 2) Collect ports: '.' cells adjacent to each crater
    ports = [[] for _ in range(K)]
    for r in range(N):
        for c in range(M):
            if grid[r][c] != '.':
                continue
            seen = set()
            for d in range(4):
                nr, nc = r + DR[d], c + DC[d]
                if in_bounds(nr, nc) and grid[nr][nc] == 'X':
                    cid = crater_id[nr][nc]
                    if cid not in seen:
                        seen.add(cid)
                        ports[cid].append((r, c))

    # BFS over '.' cells with parent pointers for path reconstruction.
    def bfs(sources, start_dist):
        dist = [[INF] * M for _ in range(N)]
        par = [[(-1, -1)] * M for _ in range(N)]
        q = deque()

        for (r, c) in sources:
            if dist[r][c] == INF:
                dist[r][c] = start_dist
                q.append((r, c))

        while q:
            r, c = q.popleft()
            for d in range(4):
                nr, nc = r + DR[d], c + DC[d]
                if in_bounds(nr, nc) and grid[nr][nc] == '.' and dist[nr][nc] == INF:
                    dist[nr][nc] = dist[r][c] + 1
                    par[nr][nc] = (r, c)
                    q.append((nr, nc))
        return dist, par

    # Ocean sources are border '.' cells
    ocean_sources = []
    for r in range(N):
        for c in range(M):
            if grid[r][c] == '.' and (r == 0 or r == N - 1 or c == 0 or c == M - 1):
                ocean_sources.append((r, c))

    dist_o, par_o = bfs(ocean_sources, 1)

    # Distances from each crater (multi-source from its ports)
    dist_c = []
    for k in range(K):
        d, _ = bfs(ports[k], 1)
        dist_c.append(d)

    # Pick best port of crater k according to distance matrix d
    def best_port(k, d):
        best = (-1, -1)
        best_val = INF
        for (r, c) in ports[k]:
            if d[r][c] < best_val:
                best_val = d[r][c]
                best = (r, c)
        return best

    # Trace path by following parent pointers until (-1,-1), return set of cells
    def trace_path(start, par):
        path = set()
        r, c = start
        while r != -1:
            path.add((r, c))
            r, c = par[r][c]
        return path

    # Candidate (a): two separate pipes
    cost = [INF] * K
    for k in range(K):
        for (r, c) in ports[k]:
            if dist_o[r][c] < cost[k]:
                cost[k] = dist_o[r][c]

    order = list(range(K))
    order.sort(key=lambda x: cost[x])

    S_sep = set()
    cost_sep = INF
    if K >= 2 and cost[order[0]] < INF and cost[order[1]] < INF:
        pa = best_port(order[0], dist_o)
        pb = best_port(order[1], dist_o)
        S_sep |= trace_path(pa, par_o)
        S_sep |= trace_path(pb, par_o)
        cost_sep = len(S_sep)

    # Candidate (b): one branched component. Enumerate pair of craters and meeting cell m.
    min_multi = INF
    best_i = best_j = -1
    best_m = (-1, -1)

    for i in range(K):
        for j in range(i + 1, K):
            for r in range(N):
                for c in range(M):
                    if grid[r][c] != '.':
                        continue
                    if dist_o[r][c] >= INF or dist_c[i][r][c] >= INF or dist_c[j][r][c] >= INF:
                        continue
                    v = dist_o[r][c] + (dist_c[i][r][c] - 1) + (dist_c[j][r][c] - 1)
                    if v < min_multi:
                        min_multi = v
                        best_i, best_j = i, j
                        best_m = (r, c)

    S_multi = set()
    cost_multi = INF
    if best_i != -1:
        # Ocean path (m -> ocean) using ocean BFS parents
        S_multi |= trace_path(best_m, par_o)

        # BFS from meeting point to reconstruct paths to crater ports
        dist_m, par_m = bfs([best_m], 0)

        pi = best_port(best_i, dist_m)
        pj = best_port(best_j, dist_m)

        S_multi |= trace_path(pi, par_m)
        S_multi |= trace_path(pj, par_m)

        cost_multi = len(S_multi)

    # Choose best solution and apply it
    chosen = S_sep if cost_sep <= cost_multi else S_multi
    for (r, c) in chosen:
        grid[r][c] = '*'

    out = "\n".join("".join(row) for row in grid)
    sys.stdout.write(out + "\n")

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