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

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int maxn = 1000;

vector<pii > directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

int n, m;
bool wall[1 + maxn + 1][1 + maxn + 1];

pii par[1 + maxn + 1][1 + maxn + 1];
int sz[1 + maxn + 1][1 + maxn + 1];

pii par_ori[1 + maxn + 1][1 + maxn + 1];
int sz_ori[1 + maxn + 1][1 + maxn + 1];

pii find_set_compress(pii cur) {
    if(cur == par[cur.fi][cur.se]) {
        return cur;
    }
    return par[cur.fi][cur.se] = find_set_compress(par[cur.fi][cur.se]);
}

void union_sets_compress(pii cur, pii nei) {
    cur = find_set_compress(cur), nei = find_set_compress(nei);
    if(cur == nei) {
        return;
    }
    if(sz[cur.fi][cur.se] > sz[nei.fi][nei.se]) {
        swap(cur, nei);
    }
    par[cur.fi][cur.se] = nei;
    sz[nei.fi][nei.se] += sz[cur.fi][cur.se];
}

void init_labyrinth(int R, int C, vector<vector<int> > L) {
    n = R, m = C;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(L[i - 1][j - 1] == 1) {
                wall[i][j] = true;
            }
        }
    }
    for(int i = 2; i <= n + 1; i++) {
        wall[i][0] = true;
    }
    for(int i = 0; i <= n - 1; i++) {
        wall[i][m + 1] = true;
    }
    for(int j = 2; j <= m + 1; j++) {
        wall[0][j] = true;
    }
    for(int j = 0; j <= m - 1; j++) {
        wall[n + 1][j] = true;
    }
    /*for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            cout << wall[i][j];
        }
        cout << "\n";
    }*/
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            par[i][j] = mp(i, j);
            sz[i][j] = 1;
        }
    }
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            if(!wall[i][j]) {
                continue;
            }
            for(pii d : directions) {
                int a = i + d.fi, b = j + d.se;
                if(a >= 0 && a <= n + 1 && b >= 0 && b <= m + 1 && wall[a][b]) {
                    union_sets_compress(mp(i, j), mp(a, b));
                }
            }
        }
    }
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            find_set_compress(mp(i, j));
        }
    }
    for(int i = 0; i <= n + 1; i++) {
        for(int j = 0; j <= m + 1; j++) {
            par_ori[i][j] = par[i][j];
            sz_ori[i][j] = sz[i][j];
        }
    }
}

vector<pii > changes;

pii find_set(pii cur) {
    if(cur == par[cur.fi][cur.se]) {
        return cur;
    }
    changes.pb(cur);
    return par[cur.fi][cur.se] = find_set(par[cur.fi][cur.se]);
}

void union_sets(pii cur, pii nei) {
    cur = find_set(cur), nei = find_set(nei);
    if(cur == nei) {
        return;
    }
    if(sz[cur.fi][cur.se] > sz[nei.fi][nei.se]) {
        swap(cur, nei);
    }
    par[cur.fi][cur.se] = nei;
    sz[nei.fi][nei.se] += sz[cur.fi][cur.se];
    changes.pb(cur);
    changes.pb(nei);
}

bool can_escape(int N, vector<int> U, vector<int> V) {
    for(int i = 0; i < N; i++) {
        int x = U[i], y = V[i];
        x++;
        y++;
        for(pii d : directions) {
            int a = x + d.fi, b = y + d.se;
            if(wall[a][b]) {
                union_sets(mp(x, y), mp(a, b));
            }
        }
    }
    bool ans = !(find_set(mp(0, 2)) == find_set(mp(2, 0)));
    for(pii p : changes) {
        par[p.fi][p.se] = par_ori[p.fi][p.se];
        sz[p.fi][p.se] = sz_ori[p.fi][p.se];
    }
    changes.clear();
    return ans;
}