Учёные Иннополиса продолжили исследование периодической таблицы. Существуют n·m известных элементов, и они представлены в периодической таблице — прямоугольнике, состоящем из n строк и m столбцов. Каждый элемент может быть описан своими координатами в таблице (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m).
Недавно учёные открыли, что для каждых четырёх различных элементов в этой таблице, которые образуют прямоугольник со сторонами, параллельными сторонам таблицы, если они имеют экземпляры трёх из четырёх элементов, то с помощью ядерного синтеза они могут произвести четвёртый элемент. Так, если имеются элементы с позиций (r1, c1), (r1, c2), (r2, c1), где r1 ≠ r2 и c1 ≠ c2, то можно произвести элемент (r2, c2).
Использованные экземпляры элементов не выбрасываются и могут быть использованы в дальнейшем для создания других элементов. Созданные элементы также могут в этом участвовать.
Учёные Иннополиса уже имеют образцы q элементов. Они хотят получить образцы всех n·m элементов таблицы. Чтобы добиться этого, они могут купить некоторые образцы в других лабораториях, а потом произвести остальные в некотором порядке. Помогите им определить, какое минимальное число элементов им надо купить.
Первая строка входных данных содержит три целых числа n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)) — размеры таблицы элементов и количество элементов, которые учёные уже имеют.
Следующие q строк содержат по два целых числа каждая: ri, ci (1 ≤ ri ≤ n, 1 ≤ ci ≤ m), которые описывают расположение уже имеющихся элементов в таблице.
Выведите минимальное количество элементов, которые надо купить.
2 2 3
1 2
2 2
2 1
0
1 5 3
1 3
1 1
1 5
2
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3
1
Каждый пример имеет иллюстрацию возможного решения. На левой части картинки крестиками показаны уже имеющиеся элементы. Правая часть картинки показывает, как оставшиеся элементы могут быть получены. Красные кружки обозначают купленные элементы, а числа в синих кружках обозначают возможный порядок, в котором эти элементы могут быть получены
Тест 1
Мы можем получить недостающий элемент ядерным синтезом, поэтому не требуется ничего покупать.
Тест 2
Так как в таблице всего один ряд, ядерный синтез не может производиться, поэтому мы вынуждены купить недостающие элементы.
Тест 3
Существует несколько возможных решений. Одно из них описано ниже.
Заметим, что непосредственно после покупки обозначенного красным элемента мы все еще не можем произвести элемент, обозначенный числом 4. Мы сможем это сделать только после получения элемента, обозначенного 1.
