Innopolis University scientists continue to investigate the periodic table. There are n·m known elements and they form a periodic table: a rectangle with n rows and m columns. Each element can be described by its coordinates (r, c) (1 ≤ r ≤ n, 1 ≤ c ≤ m) in the table.

Recently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (r_1, c_1), (r_1, c_2), (r_2, c_1), where r_1 ≠ r_2 and c_1 ≠ c_2, then we can produce element (r_2, c_2).

 [Image] 

Samples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.

Innopolis University scientists already have samples of q elements. They want to obtain samples of all n·m elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.


-----Input-----

The first line contains three integers n, m, q (1 ≤ n, m ≤ 200 000; 0 ≤ q ≤ min(n·m, 200 000)), the chemical table dimensions and the number of elements scientists already have.

The following q lines contain two integers r_{i}, c_{i} (1 ≤ r_{i} ≤ n, 1 ≤ c_{i} ≤ m), each describes an element that scientists already have. All elements in the input are different.


-----Output-----

Print the minimal number of elements to be purchased.


-----Examples-----
Input
2 2 3
1 2
2 2
2 1

Output
0

Input
1 5 3
1 3
1 1
1 5

Output
2

Input
4 3 6
1 2
1 3
2 2
2 3
3 1
3 3

Output
1



-----Note-----

For each example you have a picture which illustrates it.

The first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.

The second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.

Test 1

We can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.

 [Image] 

Test 2

We cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.

 [Image] 

Test 3

There are several possible solutions. One of them is illustrated below.

Note that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.

 [Image]

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Spanning trees

Constructive algorithms

Matrices

Starter code:

Solutions:
import sys
(n, m, q) = map(int, input().split())
p = [-1] * (n + m)
r = [0] * (n + m)

def par(i):
	if p[i] == -1:
		return i
	p[i] = par(p[i])
	return p[i]

def merge(a, b):
	(a, b) = (par(a), par(b))
	if a == b:
		return 0
	if r[a] < r[b]:
		p[a] = b
	elif r[b] < r[a]:
		p[b] = a
	else:
		p[a] = b
		r[b] += 1
	return 1
v = n + m
for l in sys.stdin.read().strip().split('\n') if q else []:
	(a, b) = map(int, l.split())
	v -= merge(a - 1, b - 1 + n)
print(v - 1)


import sys
ioRead = sys.stdin.readline
ioWrite = lambda x: sys.stdout.write(f'{x}\n')
(n, m, q) = map(int, ioRead().split(' '))
rows_and_columns = n + m
seen = [False for _ in range(rows_and_columns)]
connectsTo = [[] for _ in range(rows_and_columns)]
for _ in range(q):
	(r, c) = map(lambda x: int(x) - 1, ioRead().split(' '))
	c += n
	connectsTo[r].append(c)
	connectsTo[c].append(r)
inserts = -1
for i in range(rows_and_columns):
	if not seen[i]:
		inserts += 1
		stack = [i]
		while stack:
			current = stack.pop()
			if not seen[current]:
				seen[current] = True
				for n in connectsTo[current]:
					if not seen[n]:
						stack.append(n)
ioWrite(inserts)


from collections import deque
import os
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	(n, m, q) = map(int, input().split())
	mn = m + n
	cr = [[] for i in range(mn)]
	ca = [-1] * mn
	for i in range(q):
		(ri, ci) = map(int, input().split())
		ri -= 1
		ci -= 1
		cr[ci] += [ri + m]
		cr[ri + m] += [ci]
	ans = -1
	for i in range(mn):
		if ca[i] != -1:
			continue
		ca[i] = 1
		stack = deque()
		for j in cr[i]:
			stack.append(j)
			ca[j] = 0
		while len(stack) != 0:
			temp = stack.pop()
			for j in cr[temp]:
				if ca[j] == -1:
					ca[j] = 0
					stack.append(j)
		ans += 1
	print(ans)
main()


from sys import stdin, stdout

class UnionFind:

	def __init__(self, arr=[]):
		self.rank = {}
		self.leader = {}
		for i in arr:
			self.rank[i] = 0
			self.leader[i] = i

	def __repr__(self):
		return f' Ranks : {self.rank}, leaders : {self.leader} '

	def find(self, x):
		leader = self.leader.get(x, x)
		if leader != x:
			leader = self.find(leader)
			self.leader[x] = leader
		return leader

	def getRank(self, x):
		return self.rank.get(x, 0)

	def union(self, x, y):
		leader1 = self.find(x)
		leader2 = self.find(y)
		if leader1 == leader2:
			return False
		if self.getRank(leader1) > self.getRank(leader2):
			self.leader[leader2] = leader1
		elif self.getRank(leader1) < self.getRank(leader2):
			self.leader[leader1] = leader2
		else:
			self.leader[leader1] = leader2
			self.rank[leader2] = 1 + self.getRank(leader2)
		return True
(n, m, q) = tuple(map(int, stdin.readline().split()))
uf = UnionFind(range(1, n + m + 1))
rcs = [tuple(map(int, line.split())) for line in stdin]
grps = n + m
for (r, c) in rcs:
	if uf.union(r, c + n):
		grps -= 1
stdout.write(str(grps - 1))


from sys import stdin, stdout

class DSU:

	def __init__(self, n):
		self.root = [-1 for x in range(0, n)]

	def find(self, i):
		if self.root[i] == -1:
			return i
		else:
			self.root[i] = self.find(self.root[i])
			return self.root[i]

	def link(self, i, j):
		if self.find(i) == self.find(j):
			return False
		self.root[self.find(i)] = self.find(j)
		return True
(n, m, q) = list(map(int, stdin.readline().split()))
dsu = DSU(n + m + 1)
groups = n + m
for line in stdin:
	(r, c) = list(map(int, line.split()))
	groups -= dsu.link(r, n + c)
stdout.write(str(groups - 1) + '\n')


class UnionFind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [0] * n

	def Find(self, x):
		if self.par[x] < 0:
			return x
		else:
			self.par[x] = self.Find(self.par[x])
			return self.par[x]

	def Unite(self, x, y):
		x = self.Find(x)
		y = self.Find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[y] += self.par[x]
				self.par[x] = y
			else:
				self.par[x] += self.par[y]
				self.par[y] = x
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

	def Same(self, x, y):
		return self.Find(x) == self.Find(y)

	def Size(self, x):
		return -self.par[self.Find(x)]
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, q) = map(int, input().split())
uf = UnionFind(n + m)
for i in range(q):
	(r, c) = map(int, input().split())
	(r, c) = (r - 1, c - 1)
	uf.Unite(r, c + n)
S = set()
for i in range(n + m):
	S.add(uf.Find(i))
print(len(S) - 1)


from sys import stdin

def main():
	(n, m, q) = map(int, input().split())
	chm = list(range(n + m))
	r = [0] * (n + m)
	n -= 1
	res = n + m
	for s in stdin.read().splitlines():
		(a, b) = map(int, s.split())
		a -= 1
		b += n
		l = []
		while a != chm[a]:
			l.append(a)
			a = chm[a]
		for c in l:
			chm[c] = a
		l = []
		while b != chm[b]:
			l.append(b)
			b = chm[b]
		for c in l:
			chm[c] = b
		if a != b:
			if r[a] < r[b]:
				chm[a] = b
			elif r[b] < r[a]:
				chm[b] = a
			else:
				chm[a] = b
				r[b] += 1
			res -= 1
	print(res)
main()


(n, m, q) = map(int, input().split())
f = [-1] * (n + m + 1)

def find(x):
	if f[x] == -1:
		return x
	else:
		f[x] = find(f[x])
		return f[x]
ans = n + m - 1
for i in range(q):
	(r, c) = map(int, input().split())
	c += n
	R = find(r)
	C = find(c)
	if R != C:
		ans -= 1
		f[R] = C
print(ans)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		groups = {r: [] for r in self.roots()}
		for i in range(self.N):
			groups[self.find(i)].append(i)
		return groups

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m, q) = map(int, input().split())
uf = UnionFind(n + m)
for _ in range(q):
	(a, b) = map(int, input().split())
	uf.union(a - 1, b - 1 + n)
print(uf.group_count() - 1)


from sys import stdin

class DSU:

	def __init__(self, n) -> None:
		self.parent = [i for i in range(n)]
		self.rank = [0] * n

	def find_set(self, v):
		w = v
		parent = self.parent
		while parent[v] != v:
			v = parent[v]
		while parent[w] != w:
			t = parent[w]
			parent[w] = v
			w = t
		return v

	def union_sets(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		rank = self.rank
		if a != b:
			if rank[a] < rank[b]:
				(rank[a], rank[b]) = (rank[b], rank[a])
			self.parent[b] = a
			if rank[a] == rank[b]:
				rank[a] += 1
(n, m, q) = map(int, stdin.readline().split())
dsu = DSU(n + m)
for i in range(q):
	(r, c) = map(int, stdin.readline().split())
	r -= 1
	c -= 1
	dsu.union_sets(r, c + n)
ans = -1
for i in range(n + m):
	if dsu.parent[i] == i:
		ans += 1
print(ans)