#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class UnionFind {
    vector<int> parent, rank;
    vector<bool> leftConnected, rightConnected;
    int rows, cols;

    int getIndex(int x, int y) {
        return x * cols + y;
    }

public:
    UnionFind(int r, int c) : rows(r), cols(c) {
        int size = r * c;
        parent.resize(size);
        rank.resize(size, 0);
        leftConnected.resize(size, false);
        rightConnected.resize(size, false);
        for (int i = 0; i < size; ++i)
            parent[i] = i;
    }

    void add(int x, int y) {
        int idx = getIndex(x, y);
        // Mark connections to left and right columns
        if (y == 0) leftConnected[idx] = true;
        if (y == cols - 1) rightConnected[idx] = true;
    }

    int find(int i) {
        if (parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void unite(int x1, int y1, int x2, int y2) {
        int i1 = getIndex(x1, y1);
        int i2 = getIndex(x2, y2);
        int root1 = find(i1);
        int root2 = find(i2);
        if (root1 == root2) return;

        if (rank[root1] < rank[root2]) {
            swap(root1, root2);
        }

        parent[root2] = root1;
        if (rank[root1] == rank[root2]) rank[root1]++;

        leftConnected[root1] = leftConnected[root1] || leftConnected[root2];
        rightConnected[root1] = rightConnected[root1] || rightConnected[root2];
    }

    bool isConnectedAcross(int x, int y) {
        int idx = find(getIndex(x, y));
        return leftConnected[idx] && rightConnected[idx];
    }
};

int canStopConstruction(int n, int m, const vector<pair<int, int>>& towers) {
    UnionFind uf(n, m);
    vector<vector<bool>> grid(n, vector<bool>(m, false));
    vector<pair<int, int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};

    for (int day = 0; day < towers.size(); ++day) {
        int x = towers[day].first;
        int y = towers[day].second;
        grid[x][y] = true;
        uf.add(x, y);

        for (auto [dx, dy] : directions) {
            int nx = x + dx;
            int ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny]) {
                uf.unite(x, y, nx, ny);
            }
        }

        if (uf.isConnectedAcross(x, y)) {
            return day + 1;  // 1-indexed day
        }
    }

    return -1; // Never connected from left to right
}

int main() {
    int n = 3, m = 4;
    vector<pair<int, int>> towers = {
        {0, 0}, {1, 0}, {1, 1}, {1, 2}, {1, 3}
    };

    int stopDay = canStopConstruction(n, m, towers);
    if (stopDay != -1) {
        cout << "Construction can stop on day: " << stopDay << endl;
    } else {
        cout << "Columns never connected.\n";
    }

    return 0;
}