Description

Mingming has just answered his dad's question correctly and, of course, wants a reward. His stingy dad spots a newspaper ad: the McDonald's at their doorstep is running a promotion—there is even a free lunch. But there is a catch: you must correctly answer Ronald McDonald's question.

The question is as follows:

“There are many kids in front of me. I want you to help me find the smartest kid. In my mind, the smartest is the one who first runs into the McDonald's door. I want you to find the maximum possible difference in arrival times between the smartest and the least smart kid. However, the kids can only move according to a special rule. In front of them is an $n \times n$ grid. The bottom-left cell is the start, and the top-right cell is the door. Each child can move one cell per second in one of the four directions: up, down, left, or right. Each cell can be visited at most once. Some cells in the grid are obstacles and cannot be passed; they must be detoured.”

For example, in a $4 \times 4$ grid, cells $(1, 1), (2, 3), (4, 2)$ are obstacles. The black cells indicate one feasible route. The time is $7$.

Input Format

The first line contains two integers $n, m$.

Each of the next $m$ lines describes one obstacle, given by two integers $x, y$.

Output Format

Output a single line containing the maximum time difference.

4 3
1 1
2 3
4 2

4

Hint

Constraints: $2 \le n \le 10$, $0 \le m \le 100$, $1 \le x, y \le n$.

Translated by ChatGPT 5