题目描述

小程在一个n行n列的迷宫之中，初始时在左上角(1, 1)位置， 出口在右下角(n, n)位置。 迷宫中有m个障碍物, 障碍物和小程的初始位置和终点保证一定不重合。 小程想尽快走出迷宫，小程每次只能上下左右移动一步， 不能越过边界。请问最少他需要走多少步? 若无法到达输出-1。

输入格式

第一行两个整数分别为n和m。（$4\leq n \leq 1000$） 第2~m+1行共m行表示地图中的障碍物位置。

输出格式

输出最少的步数。

4 1
3 4

6

数据规模与约定