#include "labirintus.h"
#include <bits/stdc++.h>

using namespace std;

int r,c;
vector<vector<int> > h;
vector<vector<int> > w;
int tim=1;
bool prop[1000001];
vector<int> t[1000001]; 
vector<int> d;

void fill(int x,int y) {
    if ((!((x>=0) && (x<r) && (y>=0) && (y<c))) || (h[x][y]!=0) || (w[x][y]==0)) {
        return;
    }
    h[x][y]=tim;
    fill(x+1,y);
    fill(x-1,y);
    fill(x,y+1);
    fill(x,y-1);
    fill(x+1,y+1);
    fill(x+1,y-1);
    fill(x-1,y+1);
    fill(x-1,y-1);
}

void init_labyrinth(int R, int C, std::vector<std::vector<int>> L) {
    h=L; w=L;
    r=R; c=C;
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            h[i][j]=0;
        }
    }
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            if ((L[i][j]==1) && (h[i][j]==0)) {
                fill(i,j);
                tim++;
            }
            if (L[i][j]==0) {
                h[i][j]=tim;
                tim++;
            }
        }
    }
    for (int i=1;i<c;i++) {
        prop[h[0][i]]=1;
    }
    for (int i=0;i<r-1;i++) {
        prop[h[i][c-1]]=1;
    }
    return;
}

int db=1;
int volt[1000001];
bool ans=0;

bool dfs(int p) {
    volt[p]=db;
    for (int i:t[p]) {
        if (volt[i]!=db) {
            if (dfs(i)) {
                return(1);
            }
        }
    }
    return(prop[p]);
}

void kiir() {
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            cout << prop[h[i][j]] << " ";
        }
        cout << endl;
    }
    cout << endl;
    cout << "ans: " << ans << endl;
    cout << "db: " << db << endl;
    for (int i=0;i<r;i++) {
        for (int j=0;j<c;j++) {
            cout << w[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

bool can_escape(int N, std::vector<int> U, std::vector<int> V) {
    ans=0;
    d.clear();
    for (int i=0;i<N;i++) {
        if ((U[i] < r-1) && (h[U[i]][V[i]]!=h[U[i]+1][V[i]]) && (w[U[i]+1][V[i]]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]+1][V[i]]);
            t[h[U[i]+1][V[i]]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]+1][V[i]]);
        }
        if ((V[i] < c-1) && (h[U[i]][V[i]]!=h[U[i]][V[i]+1]) && (w[U[i]][V[i]+1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]][V[i]+1]);
            t[h[U[i]][V[i]+1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]+1]);
        }
        if ((U[i] > 0) && (h[U[i]][V[i]]!=h[U[i]-1][V[i]]) && (w[U[i]-1][V[i]]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]-1][V[i]]);
            t[h[U[i]-1][V[i]]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]-1][V[i]]);
        }
        if ((V[i] > 0) && (h[U[i]][V[i]]!=h[U[i]][V[i]-1]) && (w[U[i]][V[i]-1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]][V[i]-1]);
            t[h[U[i]][V[i]-1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]-1]);
        }
        if ((U[i] < r-1) && (V[i] < c-1) && (h[U[i]][V[i]]!=h[U[i]+1][V[i]+1]) && (w[U[i]+1][V[i]+1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]+1][V[i]+1]);
            t[h[U[i]+1][V[i]+1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]+1][V[i]+1]);
        }
        if ((U[i] < r-1) && (V[i] > 0) && (h[U[i]][V[i]]!=h[U[i]+1][V[i]-1]) && (w[U[i]+1][V[i]-1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]+1][V[i]-1]);
            t[h[U[i]+1][V[i]-1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]+1][V[i]-1]);
        }
        if ((U[i] > 0) && (V[i] < c-1) && (h[U[i]][V[i]]!=h[U[i]-1][V[i]+1]) && (w[U[i]-1][V[i]+1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]-1][V[i]+1]);
            t[h[U[i]-1][V[i]+1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]-1][V[i]+1]);
        }
        if ((U[i] > 0) && (V[i] > 0) && (h[U[i]][V[i]]!=h[U[i]-1][V[i]-1]) && (w[U[i]-1][V[i]-1]==1)) {
            t[h[U[i]][V[i]]].push_back(h[U[i]-1][V[i]-1]);
            t[h[U[i]-1][V[i]-1]].push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]][V[i]]);
            d.push_back(h[U[i]-1][V[i]-1]);
        }
        
        w[U[i]][V[i]]=1;
    }
    //kiir();
    for (int i=1;i<r;i++) {
        if (volt[h[i][0]]!=db) {
            if (dfs(h[i][0])) {
                ans=1;
                break;
            }
        }
    }
    if (ans==0) {
        for (int i=0;i<c-1;i++) {
            if (dfs(h[r-1][i])) {
                ans=1;
                break;
            }
        }
    }
    for (int i=0;i<N;i++) {
        w[U[i]][V[i]]=0;
    }
    for (int i:d) {
        t[i].clear();
    }
    db++;
    //kiir();
    return(!ans);
}