F. Альфред и Георг
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Математики Альфред и Георг играют в игру. Они берут белый клетчатый листок размером n × m клеток. Сначала Альфред раскрашивает некоторые клетки в чёрный цвет, после чего Георг должен снова перекрасить все клетки в белый. Для этого Георг сколько угодно раз проделывает следующую операцию:

  • Поместить карандаш в левый нижний угол листка (будем считать, что это точка с координатами (0, 0)), после чего нарисовать путь в верхний правый угол листка (точку с координатами (n, m)). Путь должен проходить только по границам клеток, кроме того, передвигать карандаш можно только вправо и вверх, то есть из позиции (x, y) карандаш можно передвинуть только в позиции (x + 1, y) и (x, y + 1), если при этом карандаш не покинет пределом листка.
  • Перекрасить все клетки листка, расположенные под нарисованным путём, в противоположный цвет (то есть, все белые клетки под путём перекрасить в чёрный цвет, а все чёрные — в белый). После этого нарисованный путь стирается, и (если это необходимо) Георг переходит к следующей операции.

Пока Георг работает, Альфред пытается посчитать в уме, за какое минимальное число операций можно было бы закончить игру, начиная с исходного рисунка. Для самопроверки он попросил вас написать программу, которая бы находила ответ на этот вопрос.

Входные данные

В первой строке записано три целых числа n, m и k (1 ≤ n, m ≤ 500 000, 0 ≤ k ≤ 500 000) — размеры листка и количество закрашенных клеток соответственно.

Следующие k строк описывают закрашенные клетки. i-я из этих строк содержит два целых числа xi, yi — координаты левого нижнего угла i-й закрашенной клетки в системе координат, описанной выше (0 ≤ xi < n, 0 ≤ yi < m). Гарантируется, что закрашенные клетки не повторяются.

Выходные данные

Выведите одно число — минимальное количество операций, нужное, чтобы завершить игру. Если перекрасить всю доску в белый цвет невозможно, выведите  - 1.

Примеры
Входные данные
2 2 3
0 0
1 0
1 1
Выходные данные
1
Входные данные
2 2 3
0 0
0 1
1 1
Выходные данные
2
Входные данные
2 2 3
1 0
0 1
1 1
Выходные данные
3
Примечание

В первом примере достаточно одного пути: (0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2).

Во втором примере достаточно двух путей: (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) и (0, 0) → (0, 2) → (2, 2).