## 1. Abridged problem statement

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

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

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

You must build water pipes by changing some `.` cells into `*` (pipe cells). Pipes are 4-connected through `*`/`.` adjacency, 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. Detailed editorial

### Key observations

- The grid is tiny (<= 15 x 15), so we can run many BFS computations.
- Pipes can only occupy `.` cells; `X` cells cannot be used as pipe.
- We need to connect the ocean to **at least two craters** with minimum number of pipe cells.

Model the `.` cells as vertices of an unweighted graph with edges between 4-neighbors.

A crater can be connected to the pipe network via any adjacent `.` cell ("port"). Similarly, the ocean can be connected via any border `.` cell ("ocean port").

So we have terminals:
- Ocean terminal = set of border `.` cells
- Each crater terminal k = set of `.` cells adjacent to crater k

We want a minimum-size set of `.` vertices forming a connected subgraph that touches the ocean and at least two crater terminals. But it might be cheaper to use **two disconnected pipes**: one from crater A to ocean, one from crater B to ocean.

Thus any optimal solution falls into one of two shapes:

**Shape (a): two independent connections.**
Pick two craters a, b, build a shortest path of `.` cells from a port of a to the ocean, and independently for b. The final cost is the size of the **union** of used cells (paths may overlap).

**Shape (b): one connected branched network (Steiner-like).**
Build a single connected `*` component that touches:
- the ocean, and
- ports of two craters i and j

For three terminals in an unweighted graph, an optimal Steiner tree can be seen as **three shortest paths meeting at one vertex m** (a "meeting point"). So we enumerate meeting cell m and compute:
- shortest distance from m to ocean
- shortest distance from m to crater i (via its ports)
- shortest distance from m to crater j

The union size estimate is:

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

Because `dist_o[m]` already counts m once, and each crater distance also counts m, we subtract 1 twice.

### Step-by-step algorithm

**1) Identify craters.** Flood-fill (BFS/DFS) over `X` cells, assign `crater_id[r][c]` in [0..K-1].

**2) Collect ports for each crater.** For every `.` cell, check its 4 neighbors; if neighbor is `X`, then this `.` is a port of that crater. Collect **ocean sources** = all border `.` cells.

**3) BFS distances.** BFS over `.` cells only.
- Multi-source BFS from all ocean sources: `dist_o[r][c]` = minimum number of pipe cells to connect (r,c) to ocean including (r,c) itself. Store parent pointers `par_o`.
- For each crater k, multi-source BFS from all its ports (start distance 1): `dist_c[k][r][c]`.

**4) Candidate (a): two separate pipes.** For each crater k, compute `cost[k] = min over ports p of dist_o[p]`. Pick two craters with smallest finite costs. Reconstruct the ocean paths from their best ports using `par_o`, take union set, cost is `|S_sep|`.

**5) Candidate (b): one branched network.** Enumerate crater pair i < j and meeting cell m where `grid[m]=='.'`. If all three distances are finite, compute `v = dist_o[m] + dist_c[i][m] - 1 + dist_c[j][m] - 1`. Keep the minimum v and best triple (i, j, m). To reconstruct actual cells:
- Path from m to ocean: trace `par_o` from m back to a border source.
- Run BFS from m (single-source, start distance 0), keep parents `par_m`. Choose best port of crater i and j by minimizing distance from m. Trace both port paths back to m using `par_m`.
- Union all traced cells into S_multi.

**6) Output.** Choose the smaller of S_sep and S_multi, mark those cells as `*`, print the grid.

### Correctness sketch

Any optimal solution for "at least two craters connected to ocean" is either two separate connections or one branched component. The branched shape in an unweighted graph has an optimal meeting point. Enumerating all m finds the optimal such tree.

Complexity: Let V <= 225, craters K <= 225. BFS is O(V). We do K crater BFS's plus ocean BFS plus enumeration O(K^2 V). Well within limits.

---

## 3. C++ Solution

```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;
}
```

---

## 4. Python solution (same approach, 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 visited 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 (choose two smallest crater->ocean costs)
    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()
```

---

## 5. Compressed editorial

- Flood-fill `X` cells to label each crater.
- For each crater, collect its **ports** = adjacent `.` cells. Ocean ports are border `.` cells.
- Run multi-source BFS on `.` cells:
  - from ocean ports -> `dist_o` + parents `par_o`
  - from each crater's ports -> `dist_c[k]`
- Evaluate two optimal-shape candidates:
  1. **Two separate pipes**: for each crater k, `cost[k]=min over port of dist_o[port]`; take two smallest, reconstruct both paths with `par_o`, union their cells.
  2. **One branched pipe**: for every crater pair i < j and meeting `.` cell m, minimize `dist_o[m] + dist_c[i][m]-1 + dist_c[j][m]-1`. Reconstruct union: (m->ocean via `par_o`) + (m->best port of i and j via BFS from m).
- Pick the smaller union, mark those `.` cells as `*`, print the grid.
