The Cleverest and the Least Clever

You are given an n × n grid. The starting point is at the bottom‐left cell (1,1) and the destination (the McDonald's door) is at the top‐right cell (n,n). Some cells are blocked (obstacles) and cannot be passed. Each move, a child can go one cell up, down, left, or right. A child is not allowed to visit any cell more than once.

Many children try to race from the start to the destination. The cleverest child is defined as the one who reaches the destination the fastest (i.e. using the minimum number of moves), while the least clever one is the one who takes the longest valid simple path. Your task is to compute the maximum possible difference in travel time (in seconds) between a valid shortest path and a valid longest path from the start to the destination.

If no valid path exists, output -1.

The movement rule can be formulated in LaTeX as follows:

$$\text{At each step: } (x,y) \to (x\pm1, y) \text{ or } (x,y\pm1), $$

subject to:

$$1 \le x,y \le n, \quad \text{cell is not an obstacle, and no cell is visited twice.} $$

inputFormat

The first line contains an integer n (the grid size).

The second line contains an integer m (the number of obstacles).

Each of the next m lines contains two integers x y, representing the coordinates of an obstacle. (The coordinates are 1-indexed.)

outputFormat

Print one integer: the difference between the longest and the shortest valid simple path lengths from (1,1) to (n,n). If no valid path exists, print -1.

sample

3
0

4

</p>