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

int n,m;
set<pair<int, int> > falak, orok;

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;

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

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

void unio(int a, int b) {
    a = holvan(a);
    b = holvan(b);

    if(a == b) return;

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

    p[b] = a;
    s[a] += s[b]; 
}

map<pair<int, int>, pair<int, int> > memo;

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

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

    p.resize(n*m+1);
    s.resize(n*m+1, 1);
    for(int i = 0; i < n*m; i++) p[i] = i;

    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(falak.find({fal.first+i, fal.second+j}) != falak.end()) {
                    unio(postoind(fal), postoind({fal.first+i, fal.second+j}));
                }
            }
        }
    }

    for(auto fal : falak) {
        memo[fal] = {p[postoind(fal)], s[postoind(fal)]};
    }
}

bool can_escape(int N, vector<int> U, vector<int> V){
    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(falak.find({cur.first+i, cur.second+j}) != falak.end()) {
                    unio(postoind(cur), postoind({cur.first+i, cur.second+j}));
                }

                if(orok.find({cur.first+i, cur.second+j}) != orok.end()) {
                    unio(postoind(cur), postoind({cur.first+i, cur.second+j}));
                }
            }
        }

        orok.insert(cur);
    }

    map<int, vector<pair<int, int>>> comp;

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

        comp[ind].push_back({U[i], V[i]});
    }

    for(auto fal : falak) {
        int ind = holvan(postoind(fal));

        comp[ind].push_back(fal);
    }

    bool ret = 1;
    for(auto c : comp) {
        bool b1 = 0, b2 = 0;

        for(auto i : c.second) {
            if(i.first == n-1 || i.second == 0) b1 = 1;
            if(i.first == 0 || i.second == m-1) b2 = 1;
        }

        /*cout << "component: \n";
        for(auto i : c.second) cout << i.first << ", " << i.second << endl;
        cout << "b1: " << b1 << ", b2: " << b2 << endl;
        cout << "------------------\n";*/
        
        ret &= !(b1 & b2);
    }

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

    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;
    }
    orok.clear();

    return ret;
}