E. Хоёр хэмжээст төөрдөг байшин

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

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

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

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

R2 компанийн зохион бүтээж буй хоёр хэмжээст тоглоомд $2 × n$ хэмжээтэй төөрдөг байшингаас хамгийн дөт зам олох алгоритм хэрэгтэй байв.

Төөрдөг байшинг нэгж нүднүүдэд хуваагдсан $2 × n$ хэмжээтэй тэгш өнцөгт хэлбэртэй гэж төсөөлье. Нүд бүр хоосон эсвэл саад байх болно. Хүн нэг хоромд хоосон нүднээс хөрш хоосон нүд рүү явж чадна. Хамгийн дөт замын бодлого нь дараах байдалтай өгөгдөнө. Хоёр хоосон нүд өгөгдсөнөөр нэгээс нь нөгөө рүү очих хамгийн бага хугацааг ол.

Харамсалтай нь одоогийн алгоритм зөвхөн ганц л хүсэлтэнд сайн ажиллах чадвартай боловч амьдрал дээр олон хүсэлт байгаад байв. R2-ийн ахлах програмистын хувьд чи энэхүү програмыг зохиох үүрэг авав. $2 × n$ төөрдөг байшинд олон хүсэлтэнд хариу өгч чадах програм зохио.

Оролт

Эхний мөрөнд төөрдөг байшингийн хэмжээ болон хүсэлтийн тоог илэрхийлэх $n$, $m$ $(1 ≤ n ≤ 2 \times 10^{5}; 1 ≤ m ≤ 2 \times 10^{5})$ бүхэл тоонууд байна. Дараагийн хоёр мөр төөрдөг байшинг илэрхийлнэ. Мөр бүрт $n$ тэмдэгт байх ба тэмдэгт бүр "." (хоосон нүд) эсвэл "X" (саад) байх болно.

Дараагийн $m$ мөр бүрт $v_{i}$ ба $u_{i}$ $(1 ≤ v_{i}, u_{i} ≤ 2n)$ гэсэн хоёр бүхэл тоо байх ба энэ нь $i$ дэх хүсэлтийг илэрхийлнэ. $v_{i}$, $u_{i}$ тоонууд нь чамайг $v_{i}$ дугаарын нүднээс $u_{i}$ дугаарын нүд хүрэх хамгийн богино хугацааг олох ёстойг илэрхийлнэ. Төөрдөг байшингийн эхний мөр $1$-ээс $n$ хүртэл зүүнээс баруун тийш, мөн хоёр дахь мөр $n + 1$-ээс $2n$ хүртэл зүүнээс баруун тийш дугаарлагдсан гэж үзнэ. Хүсэлтэнд буй нүднүүд бүгд хоосон байх болно.

Гаралт

$m$ мөрөнд хариуг хэвлэ. $i$ дэх мөрөнд $i$ дэх хүсэлтийн хариу буюу хамгийн богино хугацааг хэвлэ. Хэрэв очих боломжгүй бол "-1" гэж хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
4 7
.X..
...X
5 1
1 3
7 7
1 4
6 1
4 7
5 7
Гаралт
1
4
0
5
2
2
2
Оролт
10 3
X...X..X..
..X...X..X
11 7
7 18
18 10
Гаралт
9
-1
3
Сэтгэгдлүүдийг ачааллаж байна...