D. Галт уулс

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Яхаб маш том цөлд төөрчээ. Нүд бүр нь цөлийн бүс байхаар $n × n$ квадрат матрицаар цөлийг илэрхийлж болно. $(i, j)$ нь $i$-р мөр болон $j$-р $(1 ≤ i, j ≤ n)$ баганы нүдийг илэрхийлнэ. Яхаб $(i, j)$ нүднээс зөвхөн доошоо эсвэл баруун тийшээ явж чадна, энэ нүднүүд нь $(i + 1, j)$ эсвэл $(i, j + 1)$ юм.

Мөн Яхаб галт уул байгаа $m$ нүднүүдэд орж болохгүй.

Яхаб эхэндээ $(1, 1)$ нүдэнд байгаа бөгөөд $(n, n)$ нүдрүү зорчих хэрэгтэй. Яхаб нэг нүднээс өөр нэг нүдрүү зорчиход $1$ секунд хэрэгтэй гэдгийг мэддэг, тэр $(n, n)$ нүдэнд хүрч чадах хамгийн бага хугацааг ол.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{9})$, $m$ $(1 ≤ m ≤ 10^{5})$ бүхэл тоонуудыг агуудна. Дараагийн $m$ мөр бүр $x$, $y$ $(1 ≤ x, y ≤ n)$ хос бүхэл тооуудыг агуулах ба эдгээр нь галт уулсын координатыг илэрхийлнэ.

Матрицын мөрүүдийг дээрээс доош 1-ээс $n$ хүртэл, багануудыг зүүнээс баруун тийш 1-ээс $n$ хүртэл дугаарласан гэж үзнэ. $(1, 1)$ нүдэнд галт уул байхгүй. Нэг байрлалд ямар ч хоёр галт уул байхгүй.

Гаралт

Нэг бүхэл тоо хэвлэнэ, Яхаб $(n, n)$ нүдэнд хүрч чадах хамгийн богино хугацаа. Хэрвээ шийдэл байхгүй (эцсийн цэгт хүрэх зам байхгүй) бол -1 гэж хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
4 2
1 3
1 4
Гаралт
6
Оролт
7 8
1 6
2 6
3 5
3 6
4 3
5 1
5 2
5 3
Гаралт
12
Оролт
2 2
1 2
2 1
Гаралт
-1

Тэмдэглэл

Эхний жишээг авч үзье. Боломжит зам бол: $(1, 1)$ $ -> $ $(1, 2)$ $ -> $ $(2, 2)$ $ -> $ $(2, 3)$ $ -> $ $(3, 3)$ $ -> $ $(3, 4)$ $ -> $ $(4, 4)$.

Сэтгэгдлүүдийг ачааллаж байна...