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

struct me {
    int p, s;
    pair<bool, bool> b;

    me(){}

    me(int _p, int _s, pair<bool, bool> _b) : p(_p), s(_s), b(_b){} 
};

map<int, me > memo;

int n,m;
vector<vector<int> > v;
vector<pair<int, int> > falak;

int postoind(pair<int, int> pos) {
    return pos.first * m + pos.second;
}

pair<int, int> indtopos(int ind) {
    return {ind / m, ind % m};
}

vector<int> p, s;
vector<pair<bool, bool> > block;

bool mo;

int holvan(int a){
    if(p[a] == a) return a;

    return (p[a] = holvan(p[a]));
}

int holvanslow(int a) {
    if(p[a] == a) return a;
    return holvanslow(p[a]);
}

bool init;
void unio(int a, int b) {
    if(!init)a = holvanslow(a);
    else a = holvan(a);
    if(!init)b = holvanslow(b);
    else b = holvan(b);

    if(a == b) return;

    if(s[a] < s[b]) swap(a, b);

    if(!init) {
        if(memo.find(a) == memo.end()) memo[a] = {a, s[a], block[a]}; 
        if(memo.find(b) == memo.end()) memo[b] = {b, s[b], block[b]}; 
    }
    p[b] = a;
    s[a] += s[b];
    block[a] = {block[a].first | block[b].first, block[a].second | block[b].second};
    if(block[a].first && block[a].second) mo = 1;
}


void init_labyrinth(int R, int C, vector<vector<int> > L) {
    init = 1;
    mo = 0;
    n = R;
    m = C;

    v.resize(n+1, vector<int>(m+1, 0));

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            v[i][j] = L[i][j];
            if(v[i][j]) falak.push_back({i, j});
        }
    }

    p.resize(n*m+1);
    s.resize(n*m+1, 1);
    block.resize(n*m+1, {0, 0});
    for(int i = 0; i < n*m; i++) p[i] = i;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i == n-1 || j == 0) block[postoind({i, j})] = {1, 0};
            else if(i == 0 || j == m-1) block[postoind({i, j})] = {0, 1};
        }
    }

    for(auto fal : falak) {
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                if(i == 0 && j == 0) continue;

                if(fal.first + i >= 0 && fal.second+j >= 0 && v[fal.first + i][fal.second + j]) {
                    unio(postoind(fal), postoind({fal.first+i, fal.second+j}));
                }
            }
        }
    }
    init = 0;
}

bool can_escape(int N, vector<int> U, vector<int> V){
    if(mo) return 0;

    for(int i = 0; i < N; i++) {
        pair<int, int> cur = {U[i], V[i]};

        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                if(i == 0 && j == 0) continue;

                if(cur.first + i >= 0 && cur.second+j >= 0 && v[cur.first + i][cur.second + j]) {
                    unio(postoind(cur), postoind({cur.first+i, cur.second+j}));
                }
            }
        }

        v[U[i]][V[i]] = 1;
    }


    /*map<int, vector<pair<int, int>> > comp;
    for(int i = 0; i < N; i++) {
        pair<int, int> cur = {U[i], V[i]};
        int ind = holvanslow(postoind(cur));
        comp[ind].push_back(cur);
    }
    //cout << "itt1" << endl;

    for(auto i: falak) {
        int ind = holvanslow(postoind(i));
        comp[ind].push_back(i);
    }

    for(auto i : comp) {
        cout << "component: \n";
        for(auto j : i.second) cout << j.first << ", "  << j.second << endl;
        cout << "-------------\n";
    }*/

    bool ret = !mo;
    mo = 0;

    for(int i = 0; i < N; i++) {
        pair<int, int> cur = {U[i], V[i]};
        int ind = postoind(cur);

        p[ind] = ind;
        s[ind] = 1;

        v[U[i]][V[i]] = 0;
    }

    for(auto i : memo) {
        p[i.first] = i.second.p; 
        s[i.first] = i.second.s;
        block[i.first] = i.second.b; 
    }

    memo.clear();

    return ret;
}