Problem F: Great Devil Sakanikia

Problem

大悪魔サカーニャは今日も天敵の猫に襲われていた。
いつもやられている訳にはいかないので、秘密兵器を購入した。
この秘密兵器は、巨大な岩を生成することで猫の移動経路を塞ぎ、猫がこちらに近づけないようにすることができる。

今、サカーニャと一匹の猫がマス(0,0),(n−1,0),(n−1,m−1),(0,m−1)で囲まれた長方形の閉区間内にいる。
マス(0,0)に猫、マス(n−1,m−1)にサカーニャがいる。
猫は上下左右の隣接したマスに移動することができるが、区間外に出ることはできない。
いくつかのマスは、穴や障害物の影響で侵入することができない。
サカーニャは、あるマスに1つ岩を生成することでそのマスに猫が侵入できなくすることができる。
ただし、マス(0,0)とマス(n−1,m−1)に岩を生成することはできない。

マス(0,0)からマス(n−1,m−1)までの移動経路を塞ぐために必要な、生成する岩の数の最小値を求めよ。

Input

n m k
x1 y1
...
xk yk

入力はすべて整数で与えられる。
1行目にマスの大きさを表す２つの整数nとm、侵入できないマスの数kが空白区切りで与えられる。
2行目からk行に侵入できないマスの座標が与えられる。

Constraints

入力は以下の条件を満たす。

• 2 ≤ n,m ≤ 10⁵
• 0 ≤ k ≤ min(n×m−2,10⁵)
• 0 ≤ x_i ≤ n − 1
• 0 ≤ y_i ≤ m − 1
• (x_i,y_i) ≠ (x_j,y_j) (i ≠ j)
• (x_i,y_i) ≠ (0,0) ≠ (n−1,m−1)

Output

マス(0,0)からマス(n−1,m−1)までの移動経路を塞ぐために必要な、生成する岩の数の最小値を1行に出力せよ。

Sample Input 1

3 5 2
0 2
2 2

Sample Output 1

1

Sample Input 2

5 5 3
0 2
2 2
4 1

Sample Output 2

2