Есептің шарты

Сіз адасып, үлкен бір сарайға кіріп кеттіңіз. Бұл сарайдың құрылымында шаршы бөлмелер шығыс-батыс және солтүстік-оңтүстік бағыттарда тор түрінде орналасқан: шығыс-батыс бағытында $M$ баған, солтүстік-оңтүстік бағытында $N$ қатар, барлығы $M \times N$ бөлме бар. Батыстан санағанда $x$-ші бағанда ($1 \le x \le M$) және оңтүстіктен санағанда $y$-ші қатарда ($1 \le y \le N$) орналасқан бөлме $(x, y)$ деп белгіленеді.

Шығыс, батыс, оңтүстік немесе солтүстік бағытта көршілес орналасқан әрбір $2$ бөлменің арасы қабырғаның дәл ортасындағы есікпен жалғанған. Әрбір есік жабық (өтуге болмайтын) күйде немесе ашық (өтуге болатын) күйде болады. Есік ашық болған кезде, сол бөлмелердің орталықтары арасында жүріп өтуге $1$ минут кетеді. Сонымен қатар, кейбір бөлмелердің ортасында ауыстырып-қосқыш (түйме) бар; егер ауыстырып-қосқышты $1$ минут бойы үздіксіз басып тұрса, сарайдағы барлық есіктердің ашық/жабық күйі керісінше ауысады.

Қазір шығыс-батыс бағытта көршілес $2$ бөлмені жалғайтын барлық есіктер жабық, ал солтүстік-оңтүстік бағытта көршілес $2$ бөлмені жалғайтын барлық есіктер ашық. Сіз қазір $(1, 1)$ бөлмесінің ортасында тұрсыз және $(M, N)$ бөлмесінің ортасына ең қысқа уақытта жеткіңіз келеді.

Тапсырма

Сарайдың өлшемі $M, N$ және ауыстырып-қосқышы бар $K$ бөлменің орындары $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ беріледі. Шығыс-батыс бағытта көршілес $2$ бөлмені жалғайтын барлық есіктер жабық, ал солтүстік-оңтүстік бағытта көршілес $2$ бөлмені жалғайтын барлық есіктер ашық күйден бастап, $(1, 1)$ бөлмесінің ортасынан $(M, N)$ бөлмесінің ортасына дейін жетуге ең кем дегенде қанша минут кететінін табатын программа жазыңыз. Алайда, егер $(M, N)$ бөлмесіне жету мүмкін болмаса, оны көрсетіңіз.

Шектеулер

• $2 \le M \le 100000$: сарайдың шығыс-батыс бағытындағы бөлмелер саны.
• $2 \le N \le 100000$: сарайдың солтүстік-оңтүстік бағытындағы бөлмелер саны.
• $1 \le K \le 200000$: ауыстырып-қосқышы бар бөлмелер саны.
• $1 \le X_i \le M$: ауыстырып-қосқышы бар бөлменің шығыс-батыс бағытындағы орны.
• $1 \le Y_i \le N$: ауыстырып-қосқышы бар бөлменің солтүстік-оңтүстік бағытындағы орны.

Кіріс деректер

Стандартты кірістен келесі деректерді оқыңыз.

• $1$-жолда бос орындар арқылы бөлінген бүтін сандар $M, N, K$ жазылған. $M$ — сарайдың шығыс-батыс бағытындағы бөлмелер санын, $N$ — сарайдың солтүстік-оңтүстік бағытындағы бөлмелер санын, ал $K$ — ауыстырып-қосқышы бар бөлмелер санын білдіреді.
• Келесі $K$ жолдың $i$-ші жолында ($1 \le i \le K$) бос орын арқылы бөлінген бүтін сандар $X_i, Y_i$ жазылған. Бұл $(X_i, Y_i)$ бөлмесінің ортасында ауыстырып-қосқыш бар екенін білдіреді. $K$ жұп $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ өзара әртүрлі.

Шығыс деректер

Стандартты шығысқа $1$ жолда қозғалысқа кететін ең аз минут санын білдіретін бүтін санды шығарыңыз. Алайда, егер $(M, N)$ бөлмесіне жету мүмкін болмаса, оның орнына $-1$ бүтін санын шығарыңыз.

Бағалау критерийлері

• Бағалау деректерінің ішінде жалпы ұпайдың $20\%$ бөлігі үшін $M \le 1000$ және $N \le 1000$ шарттары орындалады.
• Бағалау деректерінің ішінде жалпы ұпайдың $30\%$ бөлігі үшін $K \le 2000$ шарты орындалады.
• Бағалау деректерінің ішінде жалпы ұпайдың $50\%$ бөлігі үшін осы $2$ шарттың кем дегенде біреуі орындалады. Сонымен қатар, осы $2$ шарттың екеуін де бірдей қанағаттандыратын бағалау деректері жоқ.

Мысал 1

Кіріс деректер

3 2 1
1 2

Шығыс деректер

4

Түсіндірме

Бұл мысалда келесі әрекеттер арқылы $4$ минут ішінде $(1, 1)$ бөлмесінің ортасынан $(3, 2)$ бөлмесінің ортасына жетуге болады, және бұл ең қысқа уақыт:

• $(1, 2)$ бөлмесінің ортасына өту.
• $(1, 2)$ бөлмесінің ортасындағы ауыстырып-қосқышты басу.
• $(2, 2)$ бөлмесінің ортасына өту.
• $(3, 2)$ бөлмесінің ортасына өту.

Осы кездегі сарайдың күйі төмендегі суретте көрсетілген. Суретте оң жақ бағыт — шығыс, жоғарғы бағыт — солтүстік, $\times$ белгісі сіздің орныңызды, ал $\bigcirc$ белгісі ауыстырып-қосқышты білдіреді.

Мысал 2

Кіріс деректер

3 2 1
2 1

Шығыс деректер

-1

Түсіндірме

Бұл мысалда сіз $(3, 2)$ бөлмесіне жете алмайсыз.

Мысал 3

Кіріс деректер

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

Шығыс деректер

25

Түсіндірме

Бұл мысалда сарайдың бастапқы күйі төмендегі суреттегідей. $(1, 1)$ бөлмесінің немесе $(M, N)$ бөлмесінің ортасында да ауыстырып-қосқыш болуы мүмкін екеніне назар аударыңыз.