#include "labirintus.h"
#include <bits/stdc++.h>
using namespace std;
#include <cassert>
#include <cstdio>
#include <array>
#include <vector>
#include <queue>
vector<vector<int>> d;
int n,m;
const int mxn=1005,p=1e6+5;
bool vis[mxn][mxn];
vector<array<int, 2>> dir{{0,1},{1,0},{-1,0},{0,-1}};
int lep;
int fonok[p],mer[p];
int holvan(int x)
{
    return (fonok[x]==x?x:fonok[x]=holvan(fonok[x]));
}
void unio(int a, int b, int c, int d)
{
    int x=(a-1)*m+b-1;
    int y=(c-1)*m+d-1;
    x=holvan(x);
    y=holvan(y);
    if(mer[x]>mer[y]) swap(x,y);
    mer[y]+=mer[x];
    fonok[x]=y;
}
set<array<int, 2>> last;
void init_labyrinth(int r, int c, std::vector<std::vector<int>> L) {
    n=r,m=c;
    d.assign(n+2, vector<int> (m+2, 1));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            d[i][j]=L[i-1][j-1];
            int f=(i-1)*m+j-1;
            mer[f]=1;
            fonok[f]=f;
        }
    return;
}
bool can_escape(int N, std::vector<int> u, std::vector<int> v) {
    lep++;
    if(lep==1)
    {
        for(int i=0; i<N; i++)
        {
            d[u[i]+1][v[i]+1]=1;
            last.insert({u[i],v[i]});
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(i>1 && d[i][j]==0 && d[i-1][j]==0) unio(i,j,i-1,j);
                if(j>1 && d[i][j]==0 && d[i][j-1]==0) unio(i,j,i,j-1);
            }
        }

    }
    else
    {
        set<array<int, 2>> curr;
        for(int i=0; i<N; i++)
        curr.insert({u[i],v[i]});
        vector<array<int, 2>> tor;
        for(auto &x:last)
        {
            if(curr.count(x)) continue;
            auto [a,b]=x;
            tor.push_back(x);
            a++,b++;
            d[a][b]=0;
            if(d[a+1][b]==0) unio(a+1,b,a,b);
            if(d[a-1][b]==0) unio(a-1,b,a,b);
            if(d[a][b+1]==0) unio(a,b+1,a,b);
            if(d[a][b-1]==0) unio(a,b-1,a,b);
        }
        for(auto &x:tor)
            last.erase(x);
    }
    return (holvan(0)==holvan((n-1)*m+m-1));
}

/*int main() {
    int R, C, Q;
    assert(3 == scanf("%d %d %d", &R, &C, &Q));

    std::vector<std::vector<int>> labyrinth(R, std::vector<int>(C));
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            char c;
            assert(1 == scanf(" %c", &c));
            labyrinth[i][j] = c - '0';
        }
    }
    init_labyrinth(R, C, labyrinth);

    std::vector<int> answers(Q);
    for (int i = 0; i < Q; ++i) {
        int N;
        assert(1 == scanf("%d", &N));
        std::vector<int> U(N), V(N);
        for (int j = 0; j < N; ++j) {
            assert(2 == scanf("%d %d", &U[j], &V[j]));
        }
        answers[i] = can_escape(N, U, V);
    }

    for (int i = 0; i < Q; ++i) {
        printf("%d\n", answers[i]);
    }

    return 0;
}*/