CF383B.Volcanoes

Iahub got lost in a very big desert. The desert can be represented as a n × n square matrix, where each cell is a zone of the desert. The cell (i, j) represents the cell at row i and column j (1 ≤ i, j ≤ n). Iahub can go from one cell (i, j) only down or right, that is to cells (i + 1, j) or (i, j + 1).

Also, there are m cells that are occupied by volcanoes, which Iahub cannot enter.

Iahub is initially at cell (1, 1) and he needs to travel to cell (n, n). Knowing that Iahub needs 1 second to travel from one cell to another, find the minimum time in which he can arrive in cell (n, n).

伊胡布在一片非常大的沙漠中迷路了。这片沙漠可以表示为一个 $n \times n$ 的方阵，其中每个格子代表沙漠中的一个区域。格子 $(i,\,j)$ 表示第 $i$ 行、第 $j$ 列的格子（$1 \le i,\,j \le n$）。伊胡布从格子 $(i,\,j)$ 出发时，只能向下或向右移动，即只能到达格子 $(i+1,\,j)$ 或 $(i,\,j+1)$。

此外，有 $m$ 个格子被火山占据，伊胡布不能进入这些格子。

伊胡布初始位于格子 $(1,\,1)$，他需要前往格子 $(n,\,n)$。已知伊胡布从一个格子移动到另一个格子需要 1 秒，求他到达格子 $(n,\,n)$ 所需的最少时间。

The first line contains two integers n (1 ≤ n ≤ 109) and m (1 ≤ m ≤ 105). Each of the next m lines contains a pair of integers, x and y (1 ≤ x, y ≤ n), representing the coordinates of the volcanoes.

Consider matrix rows are numbered from 1 to n from top to bottom, and matrix columns are numbered from 1 to n from left to right. There is no volcano in cell (1, 1). No two volcanoes occupy the same location.

第一行包含两个整数 $n$（$1 ≤ n ≤ 10^9$）和 $m$（$1 ≤ m ≤ 10^5$）。接下来的 $m$ 行每行包含一对整数 $x$ 和 $y$（$1 ≤ x, y ≤ n$），表示火山的坐标。

矩阵的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。单元格 $(1, 1)$ 中没有火山。任意两座火山不位于同一位置。

Print one integer, the minimum time in which Iahub can arrive at cell (n, n). If no solution exists (there is no path to the final cell), print -1.

输出一个整数，表示 Iahub 到达单元格 $(n, n)$ 所需的最少时间。如果无解（即不存在通往终点单元格的路径），则输出 -1。

Consider the first sample. A possible road is: (1, 1)  →  (1, 2)  →  (2, 2)  →  (2, 3)  →  (3, 3)  →  (3, 4)  →  (4, 4).

考虑第一个样例。一条可能的路径为：$(1,\,1) \rightarrow (1,\,2) \rightarrow (2,\,2) \rightarrow (2,\,3) \rightarrow (3,\,3) \rightarrow (3,\,4) \rightarrow (4,\,4)$。