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

vector<int> findOptimalPair(int n, int m, vector<vector<int>> blockedPositions) {
    vector<vector<int>> dist(n, vector<int>(m, -1));
    vector<vector<int>> blocked(n, vector<int>(m, 0));

    queue<pair<int,int>> q;

    for (auto &b : blockedPositions) {
        int x = b[0] - 1;
        int y = b[1] - 1;
        blocked[x][y] = 1;
        dist[x][y] = 0;
        q.push({x, y});
    }

    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

    // Multi-source BFS computes exact Manhattan distance
    while (!q.empty()) {
        auto [x,y] = q.front();
        q.pop();

        for (int k=0;k<4;k++) {
            int nx=x+dx[k];
            int ny=y+dy[k];

            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(dist[nx][ny]!=-1) continue;

            dist[nx][ny]=dist[x][y]+1;
            q.push({nx,ny});
        }
    }

    auto check = [&](int limit)->int{

        if(blocked[0][0] || blocked[n-1][m-1])
            return -1;

        if(dist[0][0] < limit || dist[n-1][m-1] < limit)
            return -1;

        vector<vector<int>> d(n, vector<int>(m,-1));

        queue<pair<int,int>> qq;
        qq.push({0,0});
        d[0][0]=0;

        while(!qq.empty()){

            auto [x,y]=qq.front();
            qq.pop();

            for(int k=0;k<4;k++){

                int nx=x+dx[k];
                int ny=y+dy[k];

                if(nx<0||nx>=n||ny<0||ny>=m)
                    continue;

                if(blocked[nx][ny])
                    continue;

                if(dist[nx][ny] < limit)
                    continue;

                if(d[nx][ny]!=-1)
                    continue;

                d[nx][ny]=d[x][y]+1;
                qq.push({nx,ny});
            }
        }

        if(d[n-1][m-1]==-1)
            return -1;

        return d[n-1][m-1]+1;
    };

    int hi=min(dist[0][0], dist[n-1][m-1]);
    int lo=0;
    int best=-1;

    while(lo<=hi){

        int mid=(lo+hi)/2;

        if(check(mid)!=-1){
            best=mid;
            lo=mid+1;
        }else{
            hi=mid-1;
        }
    }

    if(best==-1)
        return {-1,-1};

    return {best, check(best)};
}

int main() {
    // Test Case from the prompt description
    int n = 4;
    int m = 3;
    vector<vector<int>> blockedPositions = {{1, 3}, {2, 3}};
    
    // int n = 3;
    // int m = 3;
    // vector<vector<int>> blockedPositions = {{1, 2}, {2, 1}, {2, 2}};
    
    // int n = 4;
    // int m = 4;
    // vector<vector<int>> blockedPositions = {{1, 2}, {4, 3}};

    vector<int> result = findOptimalPair(n, m, blockedPositions);

    cout << "Maximum Strength: " << result[0] << endl;
    cout << "Minimum Cells Visited: " << result[1] << endl;

    // Expected Output:
    // Maximum Strength: 2
    // Minimum Cells Visited: 6

    return 0;
}