Умова
Ви заблукали й потрапили до великого маєтку. Цей маєток має структуру, в якій квадратні кімнати розташовані у вигляді сітки в напрямках схід-захід та північ-південь: $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$ та позиціями $(X_1, Y_1), (X_2, Y_2), \dots, (X_K, Y_K)$ тих $K$ кімнат, у яких є перемикачі, напишіть програму для визначення мінімальної кількості хвилин, необхідної для переміщення з центру кімнати $(1, 1)$ до центру кімнати $(M, N)$, починаючи зі стану, коли всі двері між $2$ сусідніми в напрямку схід-захід кімнатами зачинені, а всі двері між $2$ сусідніми в напрямку північ-південь кімнатами відчинені. Проте якщо дістатися кімнати $(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$ позначає кількість кімнат із перемикачем.
- В $i$-му рядку ($1 \le i \le K$) серед наступних $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)$ також може бути перемикач.
