麦当劳叔叔的难题

题目描述

话说我们铭铭小朋友成功的回答了爸爸的问题，自然少不了要去索要些奖励，抠门的爸爸一看报纸，嘿，门口的麦当劳在搞活动，还有免费午餐哦，不过前提条件：得正确回答麦当劳叔叔的问题。

问题是这样描述的：

“我面前有很多个小朋友，我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的，我希望你帮我找出最聪明和最不聪明的小朋友，可能的最大的到达时间差。但是，小朋友只能按照一个特殊的规则前进。小朋友面前有一个 $n\times n$ 的格子矩阵，左下角的格子是起点，右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子，每个格子只能经过一次。但矩阵中间有一些障碍区，不能通过，只能绕过。”

例如，$4\times 4$ 的矩阵，格子 $(1, 1),(2, 3),(4, 2)$ 为障碍区，黑格子就是一条可行的路线。时间为 $7$。

输入格式

第一行为两个整数 $n, m$。

第二至第 $m+1$ 行里，每行描述一个障碍区。用两个整数表示 $x, y$。

输出格式

仅一行，那个最大的时间差。

样例 #1

样例输入 #1

4 3
1 1
2 3
4 2

样例输出 #1

4

提示

$2\le n\le 10$，$0\le m\le 100$，$1\leq x,y\leq n$。