<|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 '' character if it contains a part of crater or with '' character if there is no crater on this square. If two squares marked with '' have the common edge they are considered as parts of one crater. There are no squares marked with '' 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 '' 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......
.............
.............
.............

: in second example you are not allowed to connect a crater with the ocean via another crater.

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

You are given an \(N \times M\) grid (\(3 \le N,M \le 15\)):

- `X` = crater cell  
- `.` = normal land cell where you may build a pipe  
- Pipes are built by converting some `.` cells into `*`.

Crater cells form connected components via 4-neighborhood; each component is one crater. No crater touches the ocean (the outside of the rectangle is ocean).

A crater is **connected to the ocean** if there exists a 4-connected chain of pipe cells `*` (on `.` cells only) that reaches any border `.` cell (ocean access), and also touches the crater along an edge.

Goal: build pipes so that **at least two distinct craters** are connected to the ocean, minimizing the number of pipe cells (`*`). Output any optimal final grid.

---

## 2) Key observations

1. **Grid is tiny** (max 225 cells), so we can do many BFS computations.
2. Pipes can only occupy `.` cells; `X` cells are blocked (and cannot be used as part of a pipe).
3. For each crater, the pipe can connect to it via any adjacent `.` cell — call these cells **ports**.
   - Ocean ports are simply border `.` cells.
4. The optimal solution has one of two “shapes”:
   - **(A) Two independent pipes**: build one ocean-connection for crater A and another for crater B (they may overlap; count union).
   - **(B) One connected network** touching ocean + crater A + crater B.  
     For 3 terminals in an unweighted graph, an optimal connecting subgraph can be represented as **three shortest paths meeting at one cell** (a “meeting point”).
5. We never need to intentionally connect **more than two** craters to reduce cost: adding terminals cannot reduce the minimum number of used cells, so the optimum for “at least two” is achieved by connecting some pair.

---

## 3) Full solution approach

### Step 0: Parse input
Read grid.

### Step 1: Identify craters (connected components of `X`)
Run BFS/DFS over `X` cells to label components with `crater_id`. Let there be \(K\) craters.

### Step 2: Collect ports
For each crater \(k\), collect all `.` cells that have an edge-adjacent `X` cell belonging to crater \(k\).  
These are the only places where pipes can “touch” crater \(k\).

Collect ocean sources: all border `.` cells.

### Step 3: BFS distance maps on `.`-cells graph
We do BFS over only `.` cells (4-neighbors).

- **Ocean BFS**: multi-source BFS from all border `.` cells.
  - `dist_o[r][c]`: min number of pipe cells to connect cell \((r,c)\) to ocean **counting the endpoint cell**.
  - Store parents `par_o` to reconstruct an actual shortest path.

- **Crater BFS for each crater \(k\)**: multi-source BFS from all its ports.
  - `dist_c[k][r][c]`: min number of cells to reach crater \(k\) (via ports), counting start.

These BFS runs are \(O(NM)\) each, cheap for \(NM \le 225\).

---

### Candidate (A): two independent pipes
For each crater \(k\):
\[
cost[k] = \min_{p \in ports[k]} dist_o[p]
\]
Pick two craters with smallest finite `cost`. Reconstruct the shortest ocean paths from their best ports using `par_o`, take the **union** of cells (overlap counted once). This union size is the true cost.

---

### Candidate (B): one connected branched network
Enumerate:
- crater pair \((i,j)\), \(i<j\)
- meeting cell \(m\) where `grid[m]=='.'`

If `dist_o[m]`, `dist_c[i][m]`, `dist_c[j][m]` are all finite, then the size of the union of three shortest paths meeting at \(m\) is:
\[
dist_o[m] + (dist_c[i][m]-1) + (dist_c[j][m]-1)
\]
(the `-1` terms prevent counting meeting cell twice).

Keep the best triple \((i,j,m)\). To reconstruct the actual set of cells:
- Use `par_o` to trace from \(m\) back to ocean.
- Run BFS from \(m\) (single-source) to get parents `par_m` and distances `dist_m`.
- Choose closest port of crater \(i\) and crater \(j\) by `dist_m[port]`.
- Trace each port back to \(m\) using `par_m`.
- Union all traced cells.

---

### Final step: choose best and output
Compare the union sizes from candidates (A) and (B). Mark those union cells as `*` (only on `.`), print grid.

**Complexity:**  
Let \(V = NM \le 225\), \(K\) craters \(\le 225\).  
BFS: \(O(KV)\). Enumeration: \(O(K^2 V)\) (still small). Fits easily.

---

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

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

static const int INF = INT_MAX;

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

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

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

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

    // ------------------------------------------------------------
    // 1) Label crater components (connected components of 'X')
    // crater_id[r][c] = component index for 'X', otherwise -1
    // ------------------------------------------------------------
    vector<vector<int>> crater_id(N, vector<int>(M, -1));
    int K = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (grid[r][c] != 'X' || crater_id[r][c] != -1) continue;

            queue<pair<int,int>> q;
            q.push({r, c});
            crater_id[r][c] = K;

            while (!q.empty()) {
                auto [cr, cc] = q.front(); q.pop();
                for (int d = 0; d < 4; d++) {
                    int nr = cr + dr[d], nc = cc + dc[d];
                    if (inside(nr, nc) && grid[nr][nc] == 'X' && crater_id[nr][nc] == -1) {
                        crater_id[nr][nc] = K;
                        q.push({nr, nc});
                    }
                }
            }
            K++;
        }
    }

    // ------------------------------------------------------------
    // 2) Collect ports for each crater:
    // ports[k] = all '.' cells adjacent to crater k
    // ------------------------------------------------------------
    vector<vector<pair<int,int>>> ports(K);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (grid[r][c] != '.') continue;

            // A '.' cell can be adjacent to multiple craters in weird cases.
            // Also avoid pushing same crater twice for the same cell.
            set<int> seen;
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (inside(nr, nc) && grid[nr][nc] == 'X') {
                    int id = crater_id[nr][nc];
                    if (seen.insert(id).second) {
                        ports[id].push_back({r, c});
                    }
                }
            }
        }
    }

    // ------------------------------------------------------------
    // BFS utility: multi-source BFS on '.' cells only.
    // dist initialized to INF, sources get start_dist.
    // Also stores parent pointers for reconstruction.
    // Parent = (-1,-1) means "this is a source".
    // ------------------------------------------------------------
    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 (!inside(nr, nc)) continue;
                if (grid[nr][nc] != '.') continue;      // can only move through land '.'
                if (dist[nr][nc] != INF) continue;      // visited

                dist[nr][nc] = dist[r][c] + 1;
                par[nr][nc] = {r, c};
                q.push({nr, nc});
            }
        }
        return pair{dist, par};
    };

    // ------------------------------------------------------------
    // 3) Ocean sources = border '.' cells
    // ------------------------------------------------------------
    vector<pair<int,int>> ocean_sources;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < M; c++) {
            if (grid[r][c] == '.' && (r == 0 || r == N-1 || c == 0 || c == M-1)) {
                ocean_sources.push_back({r, c});
            }
        }
    }

    // BFS from ocean border.
    auto [dist_o, par_o] = bfs(ocean_sources, 1);

    // BFS from each crater's ports.
    vector<vector<vector<int>>> dist_c(K);
    for (int k = 0; k < K; k++) {
        dist_c[k] = bfs(ports[k], 1).first;
    }

    // Pick best port of crater k according to a distance matrix d.
    auto best_port = [&](int k, const vector<vector<int>>& d) -> pair<int,int> {
        pair<int,int> best = {-1, -1};
        int best_val = INF;
        for (auto [r, c] : 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 source (-1,-1).
    // Returns a set of visited '.' cells to allow union counting.
    auto trace_path = [&](pair<int,int> start,
                          const vector<vector<pair<int,int>>>& par) {
        set<pair<int,int>> s;
        for (auto cur = start; cur.first != -1; cur = par[cur.first][cur.second]) {
            s.insert(cur);
        }
        return s;
    };

    // ------------------------------------------------------------
    // Candidate (A): two independent crater->ocean pipes
    // ------------------------------------------------------------
    vector<int> single_cost(K, INF);
    for (int k = 0; k < K; k++) {
        for (auto [r, c] : ports[k]) {
            single_cost[k] = min(single_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 single_cost[a] < single_cost[b];
    });

    set<pair<int,int>> S_sep;
    int cost_sep = INF;

    if (K >= 2 && single_cost[order[0]] != INF && single_cost[order[1]] != INF) {
        auto p1 = best_port(order[0], dist_o);
        auto p2 = best_port(order[1], dist_o);

        auto path1 = trace_path(p1, par_o);
        auto path2 = trace_path(p2, par_o);

        S_sep.insert(path1.begin(), path1.end());
        S_sep.insert(path2.begin(), path2.end());
        cost_sep = (int)S_sep.size();
    }

    // ------------------------------------------------------------
    // Candidate (B): one connected branched network (ocean + two craters)
    // Enumerate crater pairs and meeting cell m.
    // ------------------------------------------------------------
    int best_i = -1, best_j = -1;
    pair<int,int> best_m = {-1, -1};
    int best_val = INF;

    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) continue;
                    if (dist_c[i][r][c] == INF) continue;
                    if (dist_c[j][r][c] == INF) continue;

                    // Union size of three shortest paths meeting at (r,c).
                    int v = dist_o[r][c] + (dist_c[i][r][c] - 1) + (dist_c[j][r][c] - 1);
                    if (v < best_val) {
                        best_val = 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) {
        // 1) m -> ocean path via ocean BFS parents
        auto ocean_path = trace_path(best_m, par_o);
        S_multi.insert(ocean_path.begin(), ocean_path.end());

        // 2) BFS from meeting point to reconstruct m -> crater ports paths
        auto [dist_m, par_m] = bfs({best_m}, 0); // dist = steps from m

        // Closest ports of both craters from m
        auto pi = best_port(best_i, dist_m);
        auto pj = best_port(best_j, dist_m);

        // Trace port -> m paths via par_m
        auto path_i = trace_path(pi, par_m);
        auto path_j = trace_path(pj, par_m);

        S_multi.insert(path_i.begin(), path_i.end());
        S_multi.insert(path_j.begin(), path_j.end());

        cost_multi = (int)S_multi.size();
    }

    // ------------------------------------------------------------
    // Choose better candidate, mark '*' on selected '.' cells, output.
    // ------------------------------------------------------------
    const 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";
    }
    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)) for _ in range(N)]

    DR = (-1, 1, 0, 0)
    DC = (0, 0, -1, 1)

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

    # ------------------------------------------------------------
    # 1) Label craters (connected components of 'X')
    # ------------------------------------------------------------
    crater_id = [[-1] * M for _ in range(N)]
    K = 0
    for r in range(N):
        for c in range(M):
            if grid[r][c] != 'X' or crater_id[r][c] != -1:
                continue
            q = deque([(r, c)])
            crater_id[r][c] = K
            while q:
                cr, cc = q.popleft()
                for d in range(4):
                    nr, nc = cr + DR[d], cc + DC[d]
                    if inside(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[k] = list of (r,c) '.' cells touching crater k.
    # ------------------------------------------------------------
    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 inside(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 utility: multi-source BFS on '.' cells only.
    # sources get dist=start_dist.
    # parent[r][c] stores predecessor; (-1,-1) indicates a source.
    # ------------------------------------------------------------
    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 not inside(nr, nc):
                    continue
                if grid[nr][nc] != '.':
                    continue
                if dist[nr][nc] != INF:
                    continue
                dist[nr][nc] = dist[r][c] + 1
                par[nr][nc] = (r, c)
                q.append((nr, nc))

        return dist, par

    # ------------------------------------------------------------
    # 3) 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)

    # dist_c[k] = BFS distances from ports of crater k
    dist_c = []
    for k in range(K):
        d, _ = bfs(ports[k], 1)
        dist_c.append(d)

    def best_port(k, dist):
        """Return port of crater k minimizing dist[r][c]."""
        best = (-1, -1)
        best_val = INF
        for (r, c) in ports[k]:
            if dist[r][c] < best_val:
                best_val = dist[r][c]
                best = (r, c)
        return best

    def trace_path(start, par):
        """Follow parent pointers until (-1,-1), return set of visited cells."""
        s = set()
        r, c = start
        while r != -1:
            s.add((r, c))
            r, c = par[r][c]
        return s

    # ------------------------------------------------------------
    # Candidate (A): two independent crater->ocean pipes
    # ------------------------------------------------------------
    single_cost = [INF] * K
    for k in range(K):
        for (r, c) in ports[k]:
            single_cost[k] = min(single_cost[k], dist_o[r][c])

    order = list(range(K))
    order.sort(key=lambda k: single_cost[k])

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

    # ------------------------------------------------------------
    # Candidate (B): one connected branched network
    # Enumerate crater pairs and meeting cell m.
    # ------------------------------------------------------------
    best_i = best_j = -1
    best_m = (-1, -1)
    best_val = INF

    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:
                        continue
                    if 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 < best_val:
                        best_val = v
                        best_i, best_j = i, j
                        best_m = (r, c)

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

        # BFS from meeting point to reconstruct m->ports paths
        dist_m, par_m = bfs([best_m], 0)  # now dist_m is steps from m

        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 the best set, mark as '*', output.
    # ------------------------------------------------------------
    chosen = S_sep if cost_sep <= cost_multi else S_multi
    for (r, c) in chosen:
        grid[r][c] = '*'

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


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

If you want, I can also provide a small diagrammatic explanation of why “3 terminals ⇒ shortest paths meet at one node” is sufficient for the branched case, but the above is already enough to implement and pass within the tight time limit.