Problem: Problem

The great devil Sacagna was still attacked by her natural enemy cat today.
I bought a secret weapon because I couldn't do it all the time.
This secret weapon can block the cat's path of movement by creating huge rocks that keep cats away from you.


Now, Sacagna and one cat are in a rectangular closed section surrounded by trout (0,0), (n−1,0), (n−1, m−1), (0, m−1). I'm in.
There is a cat in the trout (0,0) and Sacagna in the trout (n−1, m−1).
Cats can move to adjacent squares on the top, bottom, left, and right, but cannot go out of the section.
Some squares cannot enter due to the effects of holes and obstacles.
Sacagna can prevent cats from invading a square by creating a rock in that square.
However, rocks cannot be formed on the trout (0,0) and the trout (n−1, m−1).

Find the minimum number of rocks to form needed to block the path of movement from trout (0,0) to trout (n−1, m−1).

Constraints

The input satisfies the following conditions.

* 2 ≤ n, m ≤ 105
* 0 ≤ k ≤ min (n × m−2,105)
* 0 ≤ xi ≤ n − 1
* 0 ≤ yi ≤ m − 1
* (xi, yi) ≠ (xj, yj) (i ≠ j)
* (xi, yi) ≠ (0,0) ≠ (n−1, m−1)

Input


n m k
x1 y1
...
xk yk


All inputs are given as integers.
On the first line, two integers n and m representing the size of the squares and the number k of the squares that cannot be penetrated are given separated by blanks.
From the second line, the coordinates of the cells that cannot enter the k line are given.

Output

Output the minimum number of rocks to be generated in one line, which is necessary to block the movement path from the mass (0,0) to the mass (n−1, m−1).

Examples

Input

3 5 2
0 2
2 2


Output

1


Input

5 5 3
0 2
2 2
4 1


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 100005

typedef pair<int,int> P;

int W,H;
int K,num_Cell;
int diff_row[8] = {-1,-1,-1,0,0,1,1,1},diff_col[8] = {-1,0,1,-1,1,-1,0,1};
int boss[6*SIZE],height[6*SIZE];
map<P,bool> MAP;
map<P,int> ID;
vector<P> V,LEFT_UP,RIGHT_UNDER,CANDIDATE;


bool rangeCheck(int row,int col){

    return row >= 0 && row <= H+1 && col >= 0 && col <= W+1;
}

int get_boss(int id){
    if(boss[id] == id)return id;
    else{
        return boss[id] = get_boss(boss[id]);
    }
}

void unite(int x,int y){
    int boss_x = get_boss(x);
    int boss_y = get_boss(y);

    if(boss_x == boss_y)return;

    //高さが高い方に吸収する
    if(height[x] > height[y]){

        boss[boss_y] = boss_x;

    }else if(height[x] < height[y]){

        boss[boss_x] = boss_y;

    }else{ //height[x] == height[y]

        boss[boss_y] = boss_x;
        height[x]++;
    }
}

int main(){

    scanf("%d %d %d",&W,&H,&K);

    num_Cell = 0;

    int x,y;

    for(int loop = 0; loop < K; loop++){

        scanf("%d %d",&x,&y);
        //外側をダミーセルで覆う
        x++;
        y++;

        MAP[make_pair(x,y)] = true;
        ID[make_pair(x,y)] = num_Cell++;
        V.push_back(make_pair(x,y));
    }

    //猫を左下に見た時、左上方向のダミーセルを列挙する
    for(int x = 0; x <= W-2; x++){

        MAP[make_pair(x,H+1)] = true;
        ID[make_pair(x,H+1)] = num_Cell++;
        LEFT_UP.push_back(make_pair(x,H+1));
    }
    for(int y = H; y >= 3; y--){

        MAP[make_pair(0,y)] = true;
        ID[make_pair(0,y)] = num_Cell++;
        LEFT_UP.push_back(make_pair(0,y));
    }

    //右下方向
    for(int y = 0; y <= H-2; y++){

        MAP[make_pair(W+1,y)] = true;
        ID[make_pair(W+1,y)] = num_Cell++;
        RIGHT_UNDER.push_back(make_pair(W+1,y));
    }
    for(int x = 3; x <= W; x++){

        MAP[make_pair(x,0)] = true;
        ID[make_pair(x,0)] = num_Cell++;
        RIGHT_UNDER.push_back(make_pair(x,0));
    }

    for(int i = 0; i < num_Cell; i++){

        boss[i] = i;
        height[i] = 0;
    }

    //左上方向のダミーセルの連結
    for(int i = 1; i < LEFT_UP.size(); i++){

        int left_id = ID[LEFT_UP[i-1]];
        int right_id = ID[LEFT_UP[i]];
        unite(left_id,right_id);
    }

    //右下方向のダミーセルの連結
    for(int i = 1; i < RIGHT_UNDER.size(); i++){

        int left_id = ID[RIGHT_UNDER[i-1]];
        int right_id = ID[RIGHT_UNDER[i]];
        unite(left_id,right_id);
    }

    //実セルの連結
    for(int i = 0; i < V.size(); i++){
        for(int a = 0; a < 8; a++){

            int adj_row = V[i].second+diff_row[a];
            int adj_col = V[i].first+diff_col[a];

            auto at = MAP.find(make_pair(adj_col,adj_row));

            if(at == MAP.end())continue;

            int my_id = ID[V[i]];
            int adj_id = ID[make_pair(adj_col,adj_row)];

            unite(my_id,adj_id);
        }
    }

    int LEFT_UP_id = ID[make_pair(0,H+1)];
    int RIGHT_UNDER_id = ID[make_pair(W+1,0)];

    if(get_boss(LEFT_UP_id) == get_boss(RIGHT_UNDER_id)){ //最初から遮断されている場合

        printf("0\n");
        return 0;
    }

    //追加1つで遮断できるか調べる
    for(int i = 0; i < V.size(); i++){
        for(int a = 0; a < 8; a++){

            int adj_row = V[i].second+diff_row[a];
            int adj_col = V[i].first+diff_col[a];

            auto at = MAP.find(make_pair(adj_col,adj_row));

            if(at != MAP.end())continue; //ダミーセル、または岩が既に置いてあったらSKIP

            CANDIDATE.push_back(make_pair(adj_col,adj_row)); //架空のセル
        }
    }

    sort(CANDIDATE.begin(),CANDIDATE.end());
    CANDIDATE.erase(unique(CANDIDATE.begin(),CANDIDATE.end()),CANDIDATE.end());

    for(int i = 0; i < CANDIDATE.size(); i++){

        bool FLG_LU = false,FLG_RD = false;

        for(int a = 0; a < 8; a++){

            int adj_row = CANDIDATE[i].second+diff_row[a];
            int adj_col = CANDIDATE[i].first+diff_col[a];

            if(!rangeCheck(adj_row,adj_col))continue;

            auto at = MAP.find(make_pair(adj_col,adj_row));

            if(at == MAP.end())continue;

            int adj_id = ID[make_pair(adj_col,adj_row)];


            if(get_boss(adj_id) == get_boss(LEFT_UP_id)){

                FLG_LU = true;

            }else if(get_boss(adj_id) == get_boss(RIGHT_UNDER_id)){

                FLG_RD = true;
            }
        }

        if(FLG_LU && FLG_RD){
            printf("1\n");
            return 0;
        }
    }

    printf("2\n");

    return 0;
}