화학 원소 표

Innopolis 대학의 과학자들은 주기율표를 계속 연구하고 있다. 이 표에는 $n \cdot m$개의 원소가 알려져 있으며, $n$개의 행과 $m$개의 열로 이루어진 직사각형 주기율표를 이룬다. 각 원소는 표에서의 좌표 $(r, c)$ ($1 \le r \le n$, $1 \le c \le m$)로 나타낼 수 있다. 최근 과학자들은 이 표에서 표의 변에 평행한 변을 가진 직사각형을 이루는 서로 다른 네 원소에 대해, 네 원소 중 세 원소의 시료를 가지고 있으면 핵융합으로 네 번째 원소의 시료를 만들 수 있다는 사실을 발견했다. 즉, $(r_1, c_1)$, $(r_1, c_2)$, $(r_2, c_1)$ 위치의 원소를 가지고 있을 때 ($r_1 \ne r_2$, $c_1 \ne c_2$), 원소 $(r_2, c_2)$를 만들 수 있다.

처음 가지고 있던 원소 시료와 새로 만든 원소 모두 이후의 핵융합에 다시 사용할 수 있다.

Innopolis 대학의 과학자들은 이미 $q$개의 원소 시료를 가지고 있다. 그들은 $n \cdot m$개의 모든 원소 시료를 얻고자 한다. 이를 위해 다른 연구소에서 시료 몇 개를 구매한 뒤, 임의의 순서로 원하는 만큼 핵융합을 하여 나머지 원소를 모두 만들 것이다. 구매해야 하는 원소 개수의 최솟값을 구하여라.

첫째 줄에는 세 정수 $n$, $m$, $q$가 주어진다 ($1 \le n, m \le 200\,000$, $0 \le q \le \min(n \cdot m, 200\,000)$). 이는 화학 표의 크기와 과학자들이 이미 가지고 있는 원소의 수이다. 다음 $q$개의 줄에는 두 정수 $r_i$, $c_i$ ($1 \le r_i \le n$, $1 \le c_i \le m$)가 주어지며, 이는 과학자들이 이미 가지고 있는 원소의 좌표이다. 입력에 주어진 원소는 모두 다르다.

한 줄에 구매해야 하는 원소 개수의 최솟값 $k$를 출력한다.

아래 그림은 예제를 설명한다.

각 예제의 첫 번째 그림은 처음에 사용할 수 있는 원소 시료 집합을 나타낸다. 검은 십자가는 실험실에 처음부터 있는 원소를 나타낸다.

두 번째 그림은 나머지 시료를 어떻게 얻을 수 있는지 나타낸다. 빨간 점선 원은 다른 연구소에서 구매해야 하는 원소를 나타낸다 (최적의 해는 빨간 원의 수를 최소화해야 한다). 파란 점선 원은 핵융합으로 만들 수 있는 원소를 나타낸다. 파란 원은 만들 수 있는 순서대로 번호가 붙는다.

예제 1

다른 세 시료로부터 핵융합을 이용해 원소를 얻을 수 있으므로 아무것도 구매할 필요가 없다.

예제 2

행이 하나뿐이므로 핵융합을 전혀 이용할 수 없어서 빠진 원소를 모두 구매해야 한다.

예제 3

원소 하나를 구매한 뒤에도 맨 위 행의 가운데 원소(4번으로 표시)는 아직 만들 수 없다. 그래서 왼쪽 아래 모서리의 원소(1번으로 표시)를 먼저 만들고, 그것을 이후의 핵융합에 사용한다.