#include <iostream>
#include <vector>
#include <queue>
#include "labirintus.h"
using namespace std;

int r,c;
vector <vector <int>> l;
vector <int> p(11e5,0);
vector <int> sz(11e5,1);
queue <int>q;
vector <int> P(11e5,0);
vector <int> SZ(11e5,1);

int holvan(int a){
    return (a==p[a]?a:holvan(p[a]));
}

void unio(int a,int b){
    a=holvan(a);
    b=holvan(b);
    if (a==b) return;
    if (sz[a]>sz[b]) swap(a,b);
    p[a]=b;
    sz[b]+=sz[a];
    q.push(a);
    q.push(b);
}

void betesz(int I,int J){
    l[I][J]=1;
    for (int i=I-1;i<=I+1;i++){
        for (int j=J-1;j<=J+1;j++){
            if (i==r || j==-1) {unio(I*c+J,r*c);continue;}
            if (i==-1 || j==c) {unio(I*c+J,r*c+1);continue;}
            if (l[i][j]) unio(I*c+J,i*c+j);
        }
    }
}

void init_labyrinth(int R, int C, vector <vector <int>> L){
    r=R;c=C;l=L;
    for (int i=0;i<r*c+2;i++) p[i]=i;
    for (int i=0;i<r;i++){
        for (int j=0;j<c;j++){
            if (l[i][j]) betesz(i,j);
        }
    }
    P=p;SZ=sz;
}

bool can_escape(int N, vector <int> U, vector <int> V){
    for (int i=0;i<N;i++) betesz(U[i],V[i]);
    bool ret=(holvan(r*c)!=holvan(r*c+1));
    for (int i=0;i<N;i++) l[U[i]][V[i]]=0;
    while(q.size()){
        p[q.front()]=P[q.front()];
        sz[q.front()]=SZ[q.front()];
        q.pop();
    }
    return ret;
}