Условие

Вы заблудились и попали в большой особняк. Этот особняк устроен так, что квадратные комнаты образуют сетку по направлениям восток-запад и север-юг: $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)$.