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

bool dfs(vector<unordered_set<int>>& adj, vector<int>& vis, vector<int>& par, int a, int b) {
    if (a == b) return true;
    vis[a] = 1;
    for (auto it : adj[a]) {
        if (!vis[it]) {
            par[it] = a;
            if (dfs(adj, vis, par, it, b)) return true;
        }
    }
    return false;
}

int getMinDistance(int v, int e, vector<int>& v1, vector<int>& v2, int a, int b) {
    vector<unordered_set<int>> adj(v);
    for (int i = 0; i < e; i++) {
        adj[v1[i]].insert(v2[i]);
        adj[v2[i]].insert(v1[i]);
    }
    
    vector<int> par(v, -1);
    vector<int> vis(v, 0);
    bool pathExists = dfs(adj, vis, par, a, b);

    if (!pathExists) {
        return -1; // No path exists between 'a' and 'b'
    }

    vector<int> path;
    for (int i = b; par[i] != -1; i = par[i]) {
        path.push_back(i);
    }
    path.push_back(a); // Include 'a' in the path
    reverse(path.begin(),path.end()); 
    int ans = 0;
    for (int i = 1; i < path.size(); i++) {
        int prev = path[i - 1];
        adj[prev].erase(path[i]);
        vector<int> vis(v, 0);
        if (!dfs(adj, vis, par, prev, b)) {
            ans++;
        }
        adj[prev].insert(path[i]);        
    }

    return ans;
}

#include <bits/stdc++.h>
vector<int> solve(int n, vector<int> &arr, int qs, vector<vector<int>> &q)
{
    // Write your code here.
    unordered_set<int> o2e, e2o;
    vector<int> ans;
    vector<int> arr_e(n),arr_o(n);
    if(n==0) return ans;
    arr_e[0]=(arr[0]%2? 0:1); arr_o[0]=(arr[0]%2 ? 1:0);
    for(int i=1;i<n;i++){
        arr_e[i]=arr_e[i-1]+(arr[i]%2? 0:1);
        arr_o[i]=arr_o[i-1]+(arr[i]%2? 1:0);
    }
    for(int i=0;i<qs;i++){
        vector<int> v=q[i];
        if(v[0]==0){
            if(v[2]%2==0 && arr[v[1]]%2!=0){
                o2e.insert(v[1]);
            }else if(v[2]%2!=0 && arr[v[1]]%2==0) e2o.insert(v[1]);
            arr[v[1]]=v[2];
        }else if(v[0]==1){
            int even=0;
            for(auto& it: o2e){
                if(it>=v[1] && it<=v[2]) even++; 
            }for(auto& it: e2o) if(it>=v[1] && it<=v[2]) even--;
            even+=(arr_e[v[2]]-(v[1]==0 ? 0: arr_e[v[1]-1]));
            ans.push_back(even);
        }else{
            int odd=0;
            for(auto& it: o2e){
                if(it>=v[1] && it<=v[2]) odd--; 
            }for(auto& it: e2o) if(it>=v[1] && it<=v[2]) odd++;
            odd+=(arr_o[v[2]]-(v[1]==0 ? 0: arr_o[v[1]-1]));
            ans.push_back(odd);

        }
    }
    return ans;
}

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

int minimumHp(int n,int m,vector<vector<int>>& board) {
    
    vector<vector<int>> dp(n, vector<int>(m));
    // The value at bottom-right should be 1 or more
    dp[n-1][m-1] = max(1, 1 - board[n-1][m-1]);

    // Initialize the last row
    for (int j = m-2; j >= 0; j--) {
        dp[n-1][j] = max(1, dp[n-1][j+1] - board[n-1][j]);
    }

    // Initialize the last column
    for (int i = n-2; i >= 0; i--) {
        dp[i][m-1] = max(1, dp[i+1][m-1] - board[i][m-1]);
    }

    // Fill up the DP table
    for (int i = n-2; i >= 0; i--) {
        for (int j = m-2; j >= 0; j--) {
            int minOnExit = min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = max(1, minOnExit - board[i][j]);
        }
    }

    return dp[0][0];
}