CF383B Volcanoes

Iahub 迷路在了一个非常大的沙漠中。这个沙漠可以表示为一个 $n \times n$ 的正方形矩阵，每个单元格表示沙漠的一个区域。单元格 $(i,j)$ 表示第 $i$ 行第 $j$ 列的单元格（$1 \le i, j \le n$）。Iahub 只能从一个单元格 $(i,j)$ 向下或者向右走，也就是只能走到 $(i+1,j)$ 或 $(i,j+1)$。 此外，有 $m$ 个单元格被火山占据，Iahub 不能进入这些单元格。 Iahub 最初在单元格 $(1,1)$，他需要到达单元格 $(n,n)$。已知 Iahub 移动到相邻的单元格需要 $1$ 秒，请你求出他到达 $(n,n)$ 的最短时间。

第一行包含两个整数 $n$（$1\le n\le 10^9$）和 $m$（$1\le m\le 10^5$）。接下来的 $m$ 行，每行包含一对整数 $x$ 和 $y$（$1\le x,y\le n$），表示火山的坐标。 规定矩阵的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。初始位置 $(1,1)$ 没有火山。任意两个火山不会出现在同一位置。

输出一个整数，表示 Iahub 到达 $(n,n)$ 的最短时间。如果无法到达（不存在通路），输出 $-1$。

参考第一个样例。一条可行的路径是：$(1,1)$ → $(1,2)$ → $(2,2)$ → $(2,3)$ → $(3,3)$ → $(3,4)$ → $(4,4)$。 由 ChatGPT 5 翻译