A bipartite graph G = (V, E) is a graph in which the vertex set V can be divided into two disjoint subsets X and Y such that every edge e ∈ E has one end point in X and the other end point in Y.

A matching M is a subset of edges such that each node in V appears in at most one edge in M.

Given a bipartite graph, find the size of the matching which has the largest size.

Constraints

* 1 ≤ |X|, |Y| ≤ 100
* 0 ≤ |E| ≤ 10,000

Input


|X| |Y| |E|
x0 y0
x1 y1
:
x|E|-1 y|E|-1


|X| and |Y| are the number of vertices in X and Y respectively, and |E| is the number of edges in the graph G. The vertices in X are named with the numbers 0, 1,..., |X|-1, and vertices in Y are named with the numbers 0, 1,..., |Y|-1, respectively.

xi and yi are the node numbers from X and Y respectevely which represent the end-points of the i-th edge.

Output

Print the largest size of the matching.

Example

Input

3 4 6
0 0
0 2
0 3
1 1
2 1
2 3


Output

3

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].add(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if not visited[adj] and adj in adj_table[current]:
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [set() for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))
INF = float('inf')

class BipartiteMatching:

	def __init__(self, n, m):
		self.n = n
		self.m = m
		self.edges = [set() for _ in range(n)]
		self.match1 = [-1] * n
		self.match2 = [-1] * m

	def dfs(self, v, visited):
		for u in self.edges[v]:
			if u in visited:
				continue
			visited.add(u)
			if self.match2[u] == -1 or self.dfs(self.match2[u], visited):
				self.match2[u] = v
				self.match1[v] = u
				return True
		return False

	def add(self, a, b):
		self.edges[a].add(b)

	def whois1(self, a):
		return self.match1[a]

	def whois2(self, a):
		return self.match2[a]

	def solve(self):
		return sum((self.dfs(i, set()) for i in range(self.n)))
(N, M, E) = MAP()
bm = BipartiteMatching(N, M)
for i in range(E):
	(x, y) = MAP()
	bm.add(x, y)
print(bm.solve())


import sys

def graph_dfs(current, matching, visited):
	for target in range(y_num):
		if not visited[target] and target in adj_table[current]:
			visited[target] = True
			if matching[target] == -1 or graph_dfs(matching[target], matching, visited):
				matching[target] = current
				return True
	return False

def mbm():
	res = 0
	matching = [-1] * y_num
	for source in range(x_num):
		visited = [False] * y_num
		if graph_dfs(source, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
adj_table = [set() for _ in range(x_num)]
for edge in edges:
	(vx, vy) = map(int, edge)
	adj_table[vx].add(vy)
print(mbm())


import sys
file_input = sys.stdin
(X, Y, E) = map(int, file_input.readline().split())
v_num = X + Y + 2
adj_mat = [[0] * v_num for i in range(v_num)]
for line in file_input:
	(x, y) = map(int, line.split())
	adj_mat[x][X + y] = 1
s = X + Y
t = s + 1
for i in range(X):
	adj_mat[s][i] = 1
for i in range(X, s):
	adj_mat[i][t] = 1
import collections

def bfs(start, goal, parent):
	unvisited = [True] * v_num
	queue = collections.deque()
	queue.append(start)
	unvisited[start] = False
	while queue:
		u = queue.popleft()
		for (v, r_capacity) in enumerate(adj_mat[u]):
			if unvisited[v] and r_capacity > 0:
				parent[v].append(u)
				queue.append(v)
				unvisited[v] = False
	return unvisited[goal]

def dfs(goal, path, parent, blocking_flow):
	v = path[-1]
	if v == goal:
		aug_path_flow = 10000
		for (x, y) in zip(path[1:], path[:-1]):
			aug_path_flow = min(aug_path_flow, adj_mat[x][y])
		for (x, y) in zip(path[1:], path[:-1]):
			adj_mat[x][y] -= aug_path_flow
			adj_mat[y][x] += aug_path_flow
		blocking_flow[0] += aug_path_flow
	else:
		for u in parent[v]:
			path.append(u)
			dfs(goal, path, parent, blocking_flow)
			path.pop()

def dinic(source, sink):
	max_flow = 0
	parent = [[] for i in range(v_num)]
	while not bfs(source, sink, parent):
		blocking_flow = [0]
		path = [sink]
		dfs(source, path, parent, blocking_flow)
		max_flow += blocking_flow[0]
		parent = [[] for i in range(v_num)]
	return max_flow
print(dinic(s, t))


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(x, y, e) = map(int, input().split())
s = x + y
t = x + y + 1
dinic = Dinic(x + y + 2)
for _ in range(e):
	(xv, yv) = map(int, input().split())
	dinic.add_edge(xv, x + yv, 1)
for xv in range(x):
	dinic.add_edge(s, xv, 1)
for yv in range(x, x + y):
	dinic.add_edge(yv, t, 1)
print(dinic.flow(s, t))


from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inp():
	return int(input())

def inpl():
	return list(map(int, input().split()))

def inpl_str():
	return list(input().split())

def FordFulkerson(S, T):
	global lines
	global cost
	global ans
	queue = deque()
	queue.append([S, INF])
	ed = [True] * N
	ed[S] = False
	route = [0 for i in range(N)]
	route[S] = -1
	while queue:
		(s, flow) = queue.pop()
		for t in lines[s]:
			if ed[t]:
				flow = min(cost[s][t], flow)
				route[t] = s
				queue.append([t, flow])
				ed[t] = False
				if t == T:
					ans += flow
					break
		else:
			continue
		break
	else:
		return False
	t = T
	s = route[t]
	while s != -1:
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow
		t = s
		s = route[t]
	return True

def PrimeFactoring(x):
	p = 2
	primes = []
	while x >= 2:
		if x % p == 0:
			primes.append(p)
			x //= p
			p = 2
		else:
			p += 1
	return primes
while True:
	(X, Y, M) = inpl()
	lines = defaultdict(set)
	N = X + Y + 2
	S = X + Y
	T = X + Y + 1
	cost = [[0] * N for _ in range(N)]
	for i in range(M):
		(x, y) = inpl()
		lines[x].add(y + X)
		cost[x][y + X] = 1
	for i in range(X):
		lines[S].add(i)
		cost[S][i] = 1
	for i in range(Y):
		lines[i + X].add(T)
		cost[i + X][T] = 1
	ans = 0
	while FordFulkerson(S, T):
		pass
	print(ans)
	break


from collections import deque

class MaxFlow:

	class Edge:

		def __init__(self, to, cap, rev):
			self.to = to
			self.cap = cap
			self.rev = rev

	def __init__(self, n, inf=10 ** 9 + 7):
		self.n = n
		self.inf = inf
		self.level = [-1] * n
		self.iter = [0] * n
		self.e = [[] for _ in range(n)]

	def add_edge(self, from_, to, cap):
		self.e[from_].append(self.Edge(to, cap, len(self.e[to])))
		self.e[to].append(self.Edge(from_, 0, len(self.e[from_]) - 1))

	def bfs(self, start):
		self.level = [-1] * self.n
		dq = deque()
		self.level[start] = 0
		dq.append(start)
		while dq:
			cur_vertex = dq.popleft()
			for edge in self.e[cur_vertex]:
				if edge.cap > 0 > self.level[edge.to]:
					self.level[edge.to] = self.level[cur_vertex] + 1
					dq.append(edge.to)

	def dfs(self, cur_vertex, end_vertex, flow):
		if cur_vertex == end_vertex:
			return flow
		while self.iter[cur_vertex] < len(self.e[cur_vertex]):
			edge = self.e[cur_vertex][self.iter[cur_vertex]]
			if edge.cap > 0 and self.level[cur_vertex] < self.level[edge.to]:
				flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
				if flowed > 0:
					edge.cap -= flowed
					self.e[edge.to][edge.rev].cap += flowed
					return flowed
			self.iter[cur_vertex] += 1
		return 0

	def compute(self, source, sink):
		flow = 0
		while True:
			self.bfs(source)
			if self.level[sink] < 0:
				return flow
			self.iter = [0] * self.n
			while True:
				f = self.dfs(source, sink, self.inf)
				if f == 0:
					break
				flow += f

def main():
	(x, y, e) = map(int, input().split())
	mf = MaxFlow(x + y + 2)
	s = x + y
	t = s + 1
	for _ in range(e):
		(a, b) = map(int, input().split())
		mf.add_edge(a, b + x, 1)
	for i in range(x):
		mf.add_edge(s, i, 1)
	for i in range(y):
		mf.add_edge(i + x, t, 1)
	print(mf.compute(s, t))
main()


def dfs(v, edges, visited, matched):
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or dfs(matched[u], edges, visited, matched):
			matched[u] = v
			return True
	return False
(xn, yn, e) = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn
for _ in range(e):
	(x, y) = map(int, input().split())
	edges[x].add(y)
print(sum((dfs(s, edges, set(), matched) for s in range(xn))))


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if adj in adj_table[current] and (not visited[adj]):
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * v_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
v_num = x_num + y_num
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


(xn, yn, e) = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

def dfs(v, visited):
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or dfs(matched[u], visited):
			matched[u] = v
			return True
	return False
for _ in range(e):
	(x, y) = map(int, input().split())
	edges[x].add(y)
print(sum((dfs(s, set()) for s in range(xn))))


import sys

def dfs(current, matching, visited):
	for target in range(y_num):
		if not visited[target] and target in adj_table[current]:
			visited[target] = True
			if matching[target] == -1 or dfs(matching[target], matching, visited):
				matching[target] = current
				return True
	return False

def mbm():
	res = 0
	matching = [-1] * y_num
	for source in range(x_num):
		visited = [False] * y_num
		if dfs(source, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
adj_table = tuple(([] for _ in range(x_num)))
for edge in edges:
	(vx, vy) = map(int, edge)
	adj_table[vx].append(vy)
print(mbm())


from collections import deque

class HopcroftKarp:

	def __init__(self, N0, N1):
		self.N0 = N0
		self.N1 = N1
		self.N = N = 2 + N0 + N1
		self.G = [[] for i in range(N)]
		for i in range(N0):
			forward = [2 + i, 1, None]
			forward[2] = backward = [0, 0, forward]
			self.G[0].append(forward)
			self.G[2 + i].append(backward)
		self.backwards = bs = []
		for i in range(N1):
			forward = [1, 1, None]
			forward[2] = backward = [2 + N0 + i, 0, forward]
			bs.append(backward)
			self.G[2 + N0 + i].append(forward)
			self.G[1].append(backward)

	def add_edge(self, fr, to):
		v0 = 2 + fr
		v1 = 2 + self.N0 + to
		forward = [v1, 1, None]
		forward[2] = backward = [v0, 0, forward]
		self.G[v0].append(forward)
		self.G[v1].append(backward)

	def bfs(self):
		G = self.G
		level = [None] * self.N
		deq = deque([0])
		level[0] = 0
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		self.level = level
		return level[1] is not None

	def dfs(self, v, t):
		if v == t:
			return 1
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w] and self.dfs(w, t):
				e[1] = 0
				rev[1] = 1
				return 1
		return 0

	def flow(self):
		flow = 0
		N = self.N
		G = self.G
		bfs = self.bfs
		dfs = self.dfs
		while bfs():
			(*self.it,) = map(iter, G)
			while dfs(0, 1):
				flow += 1
		return flow

	def matching(self):
		return [cap for (_, cap, _) in self.backwards]
import sys
readline = sys.stdin.readline
write = sys.stdout.write
(X, Y, E) = map(int, readline().split())
hc = HopcroftKarp(X, Y)
for i in range(E):
	(x, y) = map(int, readline().split())
	hc.add_edge(x, y)
write('%d\n' % hc.flow())


import collections
import queue

class Dinic:

	def __init__(self, N):
		self.N = N
		self.edges = collections.defaultdict(list)
		self.level = [0 for _ in range(self.N)]
		self.iter = [0 for _ in range(self.N)]

	def add(self, u, v, c, directed=True):
		if directed:
			self.edges[u].append([v, c, len(self.edges[v])])
			self.edges[v].append([u, 0, len(self.edges[u]) - 1])
		else:
			self.edges[u].append([v, c, len(self.edges[u])])

	def bfs(self, s):
		self.level = [-1 for _ in range(self.N)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			v = que.get(s)
			for i in range(len(self.edges[v])):
				e = self.edges[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					que.put(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.edges[v])):
			self.iter[v] = i
			e = self.edges[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.edges[e[0]][e[2]][1] += d
					return d
		return 0

	def maxFlow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.N)]
			f = self.dfs(s, t, float('inf'))
			while f > 0:
				flow += f
				f = self.dfs(s, t, float('inf'))
(X, Y, E) = map(int, input().split())
graph = Dinic(X + Y + 2)
s = X + Y
t = X + Y + 1
for i in range(X):
	graph.add(s, i, 1)
for i in range(Y):
	graph.add(X + i, t, 1)
for _ in range(E):
	(x, y) = map(int, input().split())
	graph.add(x, X + y, 1)
print(graph.maxFlow(s, t))


class BipartiteGraph(object):

	def __init__(self, num_nodes):
		self.graph = [[] for _ in range(num_nodes)]
		self.match = [None] * num_nodes

	def add_edge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def has_increasing_path(self, v, used):
		used[v] = True
		for (i, u) in enumerate(self.graph[v]):
			w = self.match[u]
			if w is None or (not used[w] and self.has_increasing_path(w, used)):
				self.match[v] = u
				self.match[u] = v
				return True
		return False

	def __str__(self):
		ret = ['graph bipartite_graph {']
		for (v, g) in enumerate(self.graph):
			for u in g:
				ret.append('    {} -- {};'.format(v, u))
		ret.append('}')
		return '\n'.join(ret)

	def solve(self):
		ret = 0
		for v in range(len(self.graph)):
			if self.match[v] is not None:
				continue
			if self.has_increasing_path(v, [False] * len(self.graph)):
				ret += 1
		return ret
(X, Y, E) = list(map(int, input().split()))
bg = BipartiteGraph(X + Y)
for _ in range(E):
	(x, y) = list(map(int, input().split()))
	y += X
	bg.add_edge(x, y)
print(bg.solve())


from collections import deque

class HopcroftKarp:

	def __init__(self, N0, N1):
		self.N0 = N0
		self.N1 = N1
		self.N = N = 2 + N0 + N1
		self.E = E = [[] for _ in range(N)]
		for end in range(N0):
			v = end + 2
			E[0].append([v, 1, len(E[v])])
			E[v].append([0, 0, len(E[0]) - 1])
		for init in range(N1):
			u = init + N0 + 2
			E[u].append([1, 1, len(E[1])])
			E[1].append([u, 0, len(E[u]) - 1])

	def add_edge(self, p1, p2):
		p1 += 2
		p2 += self.N0 + 2
		self.E[p1].append([p2, 1, len(self.E[p2])])
		self.E[p2].append([p1, 0, len(self.E[p1]) - 1])

	def _exist_augpath(self):
		self.level = level = [-1] * self.N
		E = self.E
		q = deque([(0, 0)])
		while q:
			(v, lv) = q.popleft()
			if level[v] < 0:
				level[v] = lv
				for (u, cap, _) in E[v]:
					if cap == 0 or level[u] >= 0:
						continue
					q.append((u, lv + 1))
		return level[1] >= 0

	def _blocking_flow(self):
		s = 0
		t = 1
		aug_flow = 0
		finished = [False] * self.N
		parent = [-1] * self.N
		revs = [-1] * self.N
		bottleneck = -1
		temp_flow = 0
		(level, E) = (self.level, self.E)
		stack = [(s, -1, float('inf'), -1, 0)]
		while stack:
			(v, p, f, rev, st) = stack.pop()
			if temp_flow and v != bottleneck:
				continue
			if st == 0 and (not finished[v]):
				parent[v] = p
				revs[v] = rev
				if temp_flow:
					f -= temp_flow
					temp_flow = 0
					bottleneck = -1
				if v == t:
					aug_flow += f
					if p != -1:
						stack += [(v, p, f, rev, 3)]
					continue
				n_children = 0
				for (u, cap, rev_idx) in E[v]:
					if cap == 0 or finished[u] or level[u] != level[v] + 1:
						continue
					if n_children == 0:
						stack += [(v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0)]
						n_children += 1
					else:
						stack += [(v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0)]
						n_children += 1
				if n_children == 0:
					finished[v] = True
			elif st == 1:
				continue
			elif st == 2:
				finished[v] = True
			else:
				rev_e = E[v][rev]
				e = E[p][rev_e[2]]
				e[1] -= f
				rev_e[1] += f
				if e[1] == 0:
					bottleneck = p
				if parent[p] != -1:
					stack += [(p, parent[p], f, revs[p], 3)]
				else:
					temp_flow = f
		return aug_flow

	def max_matching(self):
		matching = 0
		(exist_augpath, blocking_flow) = (self._exist_augpath, self._blocking_flow)
		while True:
			if not exist_augpath():
				break
			matching += blocking_flow()
		return matching
(N0, N1, M) = map(int, input().split())
hk = HopcroftKarp(N0, N1)
for _ in range(M):
	(u, v) = map(int, input().split())
	hk.add_edge(u, v)
print(hk.max_matching())


from heapq import heappush, heappop

class Edge:
	__slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

	def __init__(self, v, w, capacity, cost=0):
		self.src = v
		self.dest = w
		self.capacity = capacity
		self.cost = cost
		self.flow = 0

	def other(self, v):
		if v == self.src:
			return self.dest
		else:
			return self.src

	def residual_capacity(self, v):
		if v == self.src:
			return self.capacity - self.flow
		else:
			return self.flow

	def cost_from(self, v):
		if v == self.src:
			return self.cost
		else:
			return -self.cost

	def add_flow(self, v, f):
		if v == self.src:
			self.flow += f
		else:
			self.flow -= f

	def __str__(self):
		return '{} {} {} {} {}'.format(self.src, self.dest, self.capacity, self.cost, self.flow)

class Network:

	def __init__(self, v):
		self.v = v
		self._edges = [[] for _ in range(v)]

	def add(self, edge):
		self._edges[edge.src].append(edge)
		self._edges[edge.dest].append(edge)

	def adj(self, v):
		return self._edges[v]

	def flow(self, v):
		return sum((e.flow for e in self.adj(v) if e.src == v))

	def cost(self):
		cost = 0
		for v in range(self.v):
			for e in self.adj(v):
				if e.src == v:
					cost += e.flow * e.cost
		return cost

	def __str__(self):
		s = ''
		for v in range(self.v):
			for e in self.adj(v):
				s += '{} {}\n'.format(v, e)
		return s

def max_flow(network, s, t):

	def augment_path():
		marked = [False] * network.v
		edge_to = [None] * network.v
		n = 0
		heap = [(-10 ** 6, s, n, None)]
		while heap:
			(cap, v, _, e) = heappop(heap)
			edge_to[v] = e
			if v == t:
				return (-cap, edge_to)
			if not marked[v]:
				marked[v] = True
				for ne in network.adj(v):
					n += 1
					w = ne.other(v)
					c = ne.residual_capacity(v)
					if not marked[w] and c > 0:
						heappush(heap, (max(-c, cap), w, n, ne))
		return (0, [])
	while True:
		(cap, path) = augment_path()
		if cap == 0:
			break
		v = t
		e = path[t]
		while e is not None:
			v = e.other(v)
			e.add_flow(v, cap)
			e = path[v]
	return network.flow(s)

def run():
	(n, m, e) = [int(i) for i in input().split()]
	(s, t) = (0, n + m + 1)
	net = Network(n + m + 2)
	for i in range(n):
		net.add(Edge(s, i + 1, 1))
	for j in range(m):
		net.add(Edge(j + 1 + n, t, 1))
	for _ in range(e):
		(x, y) = [int(i) for i in input().split()]
		edge = Edge(x + 1, y + 1 + n, 1)
		net.add(edge)
	print(max_flow(net, s, t))
run()


class BipartiteMatching:

	def __init__(self, v: int):
		self.v = v
		self.g = [[] for _ in range(v)]
		self.match = [-1] * v
		self.used = [False] * v

	def add_edge(self, u, v):
		self.g[u].append(v)
		self.g[v].append(u)

	def dfs(self, v):
		self.used[v] = True
		for i in range(len(self.g[v])):
			u = self.g[v][i]
			w = self.match[u]
			if w < 0 or (not self.used[w] and self.dfs(w)):
				self.match[u] = v
				self.match[v] = u
				return True
		return False

	def maximum_matching(self):
		res = 0
		self.match = [-1] * self.v
		for i in range(self.v):
			if self.match[i] < 0:
				self.used = [False] * self.v
				if self.dfs(i):
					res += 1
		return res
(x_size, y_size, e) = map(int, input().split())
b = BipartiteMatching(x_size + y_size)
for i in range(e):
	(x, y) = map(int, input().split())
	b.add_edge(x, y + x_size)
print(b.maximum_matching())


from collections import defaultdict

def dfs(here, used, match, connect):
	used[here] = 1
	for near in connect[here]:
		m = match[near]
		if m < 0 or (not used[m] and dfs(m, used, match, connect)):
			match[here] = near
			match[near] = here
			return 1
	return 0
(a_num, b_num, e_num) = (int(n) for n in input().split(' '))
connect = defaultdict(list)
all_v = a_num + b_num
match = [-1 for n in range(all_v)]
for _ in range(e_num):
	(v1, v2) = (int(n) for n in input().split(' '))
	v2 += a_num
	connect[v1].append(v2)
	connect[v2].append(v1)
answer = 0
for i in range(all_v):
	if match[i] < 0:
		used = [0 for n in range(all_v)]
		if dfs(i, used, match, connect):
			answer += 1
print(answer)


import sys
file_input = sys.stdin
(X, Y, E) = map(int, file_input.readline().split())
v_num = X + Y + 2
adj_mat = [[0] * v_num for i in range(v_num)]
for line in file_input:
	(x, y) = map(int, line.split())
	adj_mat[x][X + y] = 1
s = X + Y
t = s + 1
for i in range(X):
	adj_mat[s][i] = 1
for i in range(X, s):
	adj_mat[i][t] = 1
import collections

def bfs(start, goal, parent):
	level = [v_num] * v_num
	unvisited = [True] * v_num
	queue = collections.deque()
	queue.append(start)
	level[start] = 0
	unvisited[start] = False
	while queue:
		u = queue.popleft()
		next_level = level[u] + 1
		for (v, r_capacity) in enumerate(adj_mat[u]):
			if level[v] >= next_level and r_capacity > 0:
				level[v] = next_level
				parent[v].append(u)
				if unvisited[v]:
					queue.append(v)
					unvisited[v] = False
	return level[goal]

def dfs(goal, path, parent, blocking_flow):
	v = path[-1]
	if v == goal:
		aug_path_flow = 10000
		for (x, y) in zip(path[1:], path[:-1]):
			aug_path_flow = min(aug_path_flow, adj_mat[x][y])
		for (x, y) in zip(path[1:], path[:-1]):
			adj_mat[x][y] -= aug_path_flow
			adj_mat[y][x] += aug_path_flow
		blocking_flow[0] += aug_path_flow
	else:
		for u in parent[v]:
			path.append(u)
			dfs(goal, path, parent, blocking_flow)
			path.pop()

def dinic(source, sink):
	max_flow = 0
	parent = [[] for i in range(v_num)]
	while bfs(source, sink, parent) != v_num:
		blocking_flow = [0]
		path = [sink]
		dfs(source, path, parent, blocking_flow)
		max_flow += blocking_flow[0]
		parent = [[] for i in range(v_num)]
	return max_flow
print(dinic(s, t))


import sys

def dfs(current, matching, visited):
	for target in range(y_num):
		if not visited[target] and target in adj_table[current]:
			visited[target] = True
			if matching[target] == -1 or dfs(matching[target], matching, visited):
				matching[target] = current
				return True
	return False

def mbm():
	res = 0
	matching = [-1] * y_num
	for source in range(x_num):
		visited = [False] * y_num
		if dfs(source, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
adj_table = tuple((set() for _ in range(x_num)))
for edge in edges:
	(vx, vy) = map(int, edge)
	adj_table[vx].add(vy)
print(mbm())


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def bfs(s, g, n):
	bfs_map = [-1 for i in range(n)]
	bfs_map[s] = 0
	q = deque()
	q.append(s)
	fin = False
	while q:
		x = q.popleft()
		for y in range(n):
			if c[x][y] > 0 and bfs_map[y] < 0:
				bfs_map[y] = bfs_map[x] + 1
				if y == g:
					fin = True
					break
				q.append(y)
		if fin:
			break
	if bfs_map[g] == -1:
		return [None, 0]
	path = [None for i in range(bfs_map[g] + 1)]
	m = float('inf')
	path[bfs_map[g]] = g
	y = g
	for i in range(bfs_map[g])[::-1]:
		for x in range(n + 1):
			if c[x][y] > 0 and bfs_map[x] == bfs_map[y] - 1:
				path[i] = x
				if c[x][y] < m:
					m = c[x][y]
				y = x
				break
	return [path, m]

def ford_fulkerson(s, g, c, n):
	while 1:
		(p, m) = bfs(s, g, n)
		if not m:
			break
		for i in range(len(p) - 1):
			c[p[i]][p[i + 1]] -= m
			c[p[i + 1]][p[i]] += m
	return sum(c[g])
(x, y, e) = LI()
c = [[0 for i in range(x + y + 2)] for j in range(x + y + 2)]
for i in range(x):
	c[0][i + 1] = 1
for i in range(y):
	c[x + i + 1][x + y + 1] = 1
for i in range(e):
	(a, b) = LI()
	c[a + 1][x + b + 1] = 1
print(ford_fulkerson(0, x + y + 1, c, x + y + 2))


class BipartiteMatching:

	def __init__(self, V1, V2):
		self.V1 = V1
		self.V2 = V2
		self.V = V1 + V2
		self.graph = [[] for _ in range(V1 + V2)]

	def add_edge(self, v1, v2):
		v2 += self.V1
		self.graph[v1].append(v2)
		self.graph[v2].append(v1)

	def dfs(self, s):
		self.par = [None] * self.V
		self.used = [False] * self.V
		self.used[s] = True
		self.stack = [s]
		while self.stack:
			v = self.stack.pop()
			for nv in self.graph[v]:
				w = self.match[nv]
				if w < 0:
					while True:
						self.match[v] = nv
						self.match[nv] = v
						if v == s:
							return True
						(v, nv) = self.par[v]
				elif not self.used[w]:
					self.par[w] = (v, nv)
					self.used[w] = True
					self.stack.append(w)
		return False

	def bipartite_matching(self):
		res = 0
		self.match = [-1] * self.V
		for v in range(self.V):
			if self.match[v] < 0:
				if self.dfs(v):
					res += 1
		return res
import sys
input = sys.stdin.readline
(V1, V2, E) = map(int, input().split())
bm = BipartiteMatching(V1, V2)
for _ in range(E):
	(a, b) = map(int, input().split())
	bm.add_edge(a, b)
print(bm.bipartite_matching())


def dfs(v, visited):
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or dfs(matched[u], visited):
			matched[u] = v
			return True
	return False
(xn, yn, e) = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn
for _ in range(e):
	(x, y) = map(int, input().split())
	edges[x].add(y)
print(sum(map(lambda s: dfs(s, set()), range(xn))))


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if not visited[adj] and adj in adj_table[current]:
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline
edge = namedtuple('edge', ['to', 'cap', 'rev'])

def add_edge(G, f, t, c):
	G[f].append(edge(t, c, len(G[t])))
	G[t].append(edge(f, 0, len(G[f]) - 1))

def dfs(G, used, v, t, f):
	if v == t:
		return f
	used[v] = True
	for i in range(len(G[v])):
		e = G[v][i]
		if not used[e.to] and e.cap > 0:
			d = dfs(G, used, e.to, t, min(f, e.cap))
			if d > 0:
				G[v][i] = edge(e.to, e.cap - d, e.rev)
				G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
				return d
	return 0

def max_flow(G, V, s, t):
	flow = 0
	while True:
		used = [False] * V
		f = dfs(G, used, s, t, float('inf'))
		if f == 0:
			return flow
		flow += f

def main(args):
	(X, Y, E) = map(int, input().split())
	G = [[] for _ in range(X + Y + 2)]
	for li in range(E):
		(x, y) = map(int, input().split())
		add_edge(G, x + 1, X + y + 1, 1)
	for x in range(1, X + 1):
		add_edge(G, 0, x, 1)
	for y in range(X + 1, X + Y + 1):
		add_edge(G, y, X + Y + 1, 1)
	ans = max_flow(G, X + Y + 2, 0, X + Y + 1)
	print(ans)
main(sys.argv[1:])


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	(X, Y, E) = LI()
	edge = [set() for _ in range(X + Y + 2)]
	for _ in range(E):
		(a, b) = LI()
		i = a + 1
		j = b + X + 1
		edge[i].add(j)
	for i in range(1, X + 1):
		edge[0].add(i)
	for j in range(X + 1, X + Y + 1):
		edge[j].add(X + Y + 1)
	ans = 0
	while True:
		node = [-2] * (X + Y + 2)
		node[0] = -1
		q = collections.deque()
		q.append(0)
		while q:
			u = q.pop()
			for v in edge[u]:
				if v == X + Y + 1:
					ans += 1
					node[v] = u
					break
				if node[v] < -1:
					node[v] = u
					q.append(v)
			else:
				continue
			break
		else:
			break
		u = X + Y + 1
		while node[u] >= 0:
			edge[node[u]].remove(u)
			edge[u].add(node[u])
			u = node[u]
	print(ans)
main()


def dfs(s):
	return _dfs(s, set())

def _dfs(v, visited):
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or _dfs(matched[u], visited):
			matched[u] = v
			return True
	return False
(xn, yn, e) = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn
for _ in range(e):
	(x, y) = map(int, input().split())
	edges[x].add(y)
print(sum(map(dfs, range(xn))))


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if adj in adj_table[current] and (not visited[adj]):
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
v_num = x_num + y_num
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import collections

class Dinic:

	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		self.g[fr].append([to, cap, len(self.g[to])])
		self.g[to].append([fr, 0, len(self.g[fr]) - 1])

	def add_multi_edge(self, v1, v2, cap1, cap2):
		self.g[v1].append([v2, cap1, len(self.g[v2])])
		self.g[v2].append([v1, cap2, len(self.g[v1]) - 1])

	def bfs(self, s):
		level = [-1] * self.n
		deq = collections.deque()
		level[s] = 0
		deq.append(s)
		while deq:
			v = deq.popleft()
			for e in self.g[v]:
				if e[1] > 0 and level[e[0]] < 0:
					level[e[0]] = level[v] + 1
					deq.append(e[0])
		self.level = level

	def dfs(self, v, t, f):
		if v == t:
			return f
		es = self.g[v]
		level = self.level
		for i in range(self.it[v], len(self.g[v])):
			e = es[i]
			if e[1] > 0 and level[v] < level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.g[e[0]][e[2]][1] += d
					self.it[v] = i
					return d
		self.it[v] = len(self.g[v])
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				break
			self.it = [0] * self.n
			while True:
				f = self.dfs(s, t, 10 ** 9 + 7)
				if f > 0:
					flow += f
				else:
					break
		return flow
(X, Y, E) = map(int, input().split())
dinic = Dinic(2 + X + Y)
for i in range(X):
	dinic.add_edge(0, 2 + i, 1)
for i in range(Y):
	dinic.add_edge(2 + X + i, 1, 1)
for i in range(E):
	(x, y) = map(int, input().split())
	dinic.add_edge(2 + x, 2 + X + y, 1)
print(dinic.max_flow(0, 1))


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].add(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for target in range(y_num):
		if not visited[target] and target in adj_table[current]:
			visited[target] = True
			if matching[target] == -1 or graph_dfs(matching[target], matching, visited):
				matching[target] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for source in range(x_num):
		visited = [False] * y_num
		if graph_dfs(source, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [set() for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if not visited[adj] and adj in adj_table[current]:
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import sys
file_input = sys.stdin
(X, Y, E) = map(int, file_input.readline().split())
v_num = X + Y + 2
adj_mat = [[0] * v_num for i in range(v_num)]
for line in file_input:
	(x, y) = map(int, line.split())
	adj_mat[x][X + y] = 1
s = X + Y
t = s + 1
for i in range(X):
	adj_mat[s][i] = 1
for i in range(X, s):
	adj_mat[i][t] = 1
import collections

def bfs(start, goal, parent):
	unvisited = [True] * v_num
	queue = collections.deque()
	queue.append(start)
	unvisited[start] = False
	while queue:
		u = queue.popleft()
		for (v, r_capacity) in enumerate(adj_mat[u]):
			if unvisited[v] and r_capacity > 0:
				queue.append(v)
				unvisited[v] = False
				parent[v] = u
				if v == goal:
					return not unvisited[goal]

def ford_fulkerson(source, sink):
	parent = [None] * v_num
	max_flow = 0
	while bfs(source, sink, parent):
		aug_path_flow = 10000
		v = sink
		while v != source:
			aug_path_flow = min(aug_path_flow, adj_mat[parent[v]][v])
			v = parent[v]
		max_flow += aug_path_flow
		v = sink
		while v != source:
			u = parent[v]
			adj_mat[u][v] -= aug_path_flow
			adj_mat[v][u] += aug_path_flow
			v = u
	return max_flow
print(ford_fulkerson(s, t))


def read_data():
	(X, Y, E) = map(int, input().split())
	Ss = list(range(X))
	Ts = list(range(X, X + Y))
	Es = []
	for i in range(E):
		(x, y) = map(int, input().split())
		Es.append((x, y + X))
	return (Ss, Ts, Es)

def bp_match(Ss, Ts, Es):
	super_source = len(Ss) + len(Ts)
	super_target = super_source + 1
	Cs = [dict() for i in range(super_target + 1)]
	for (si, ti) in Es:
		Cs[si][ti] = 1
		Cs[ti][si] = 0
	for si in Ss:
		Cs[super_source][si] = 1
		Cs[si][super_source] = 0
	for ti in Ts:
		Cs[super_target][ti] = 0
		Cs[ti][super_target] = 1
	return dinic(Cs, super_target + 1, super_source, super_target)

def dinic(cf, nV, s, t):
	dist = get_distance(cf, s, t)
	while dist[t] > 0:
		df = dfs(dist, cf, s, t, float('inf'))
		while df:
			df = dfs(dist, cf, s, t, float('inf'))
		dist = get_distance(cf, s, t)
	return sum(cf[t].values())

def get_distance(cf, s, t):
	dist = [-1] * len(cf)
	dist[s] = 0
	frontiers = [s]
	while frontiers:
		new_frontiers = []
		for u in frontiers:
			for (v, capacity) in cf[u].items():
				if dist[v] == -1 and capacity > 0:
					dist[v] = dist[u] + 1
					new_frontiers.append(v)
		frontiers = new_frontiers
	return dist

def dfs(dist, cf, u, t, df):
	if u == t:
		return df
	for (v, capacity) in cf[u].items():
		if dist[v] > dist[u] and capacity > 0:
			new_df = dfs(dist, cf, v, t, min(df, capacity))
			if new_df > 0:
				cf[u][v] -= new_df
				cf[v][u] += new_df
				return new_df
	return 0
(Ss, Ts, Es) = read_data()
print(bp_match(Ss, Ts, Es))


import sys
from collections import deque

class MaxFlow:

	class Edge:

		def __init__(self, to, cap, rev):
			(self.to, self.cap, self.rev) = (to, cap, rev)

	def __init__(self, node_size, inf):
		self._node = node_size
		self._inf = inf
		self._level = [-1] * self._node
		self._iter = [0] * self._node
		self._graph = [[] for _ in range(self._node)]

	def add_edge(self, from_, to, cap):
		self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
		self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

	def bfs(self, start):
		self._level = [-1] * self._node
		que = deque()
		self._level[start] = 0
		que.append(start)
		while que:
			cur_vertex = que.popleft()
			for e in self._graph[cur_vertex]:
				if self._level[e.to] < 0 < e.cap:
					self._level[e.to] = self._level[cur_vertex] + 1
					que.append(e.to)

	def dfs(self, cur_vertex, end_vertex, flow):
		if cur_vertex == end_vertex:
			return flow
		for e in self._graph[cur_vertex][self._iter[cur_vertex]:len(self._graph[cur_vertex])]:
			if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
				flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
				if flowed > 0:
					e.cap -= flowed
					self._graph[e.to][e.rev].cap += flowed
					return flowed
		return 0

	def solve(self, source, sink):
		flow = 0
		while True:
			self.bfs(source)
			if self._level[sink] < 0:
				return flow
			self._iter = [0] * self._node
			while True:
				f = self.dfs(source, sink, self._inf)
				if f == 0:
					break
				flow += f

class BipartiteMatching:

	def __init__(self, size1, size2):
		(self._u_size, self._v_size) = (size1, size2)
		self.mf = MaxFlow(self._u_size + self._v_size + 2, min(self._u_size, self._v_size))
		for i in range(self._u_size):
			self.mf.add_edge(0, i + 1, 1)
		for i in range(self._v_size):
			self.mf.add_edge(self._u_size + i + 1, self._u_size + self._v_size + 1, 1)

	def add_edge(self, from_, to):
		self.mf.add_edge(from_ + 1, to + self._u_size + 1, 1)

	def solve(self):
		return self.mf.solve(0, self._u_size + self._v_size + 1)
(x, y, m) = map(int, sys.stdin.readline().split())
bm = BipartiteMatching(x, y)
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	bm.add_edge(u, v)
print(bm.solve())


import sys
from collections import deque

class MaxFlow:

	class Edge:

		def __init__(self, to, cap, rev):
			(self.to, self.cap, self.rev) = (to, cap, rev)

	def __init__(self, node_size, inf):
		self._node = node_size
		self._inf = inf
		self._level = [-1] * self._node
		self._iter = [0] * self._node
		self._graph = [[] for _ in range(self._node)]

	def add_edge(self, from_, to, cap):
		self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
		self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_]) - 1))

	def bfs(self, start):
		self._level = [-1] * self._node
		que = deque()
		self._level[start] = 0
		que.append(start)
		while que:
			cur_vertex = que.popleft()
			for e in self._graph[cur_vertex]:
				if self._level[e.to] < 0 < e.cap:
					self._level[e.to] = self._level[cur_vertex] + 1
					que.append(e.to)

	def dfs(self, cur_vertex, end_vertex, flow):
		if cur_vertex == end_vertex:
			return flow
		while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
			e = self._graph[cur_vertex][self._iter[cur_vertex]]
			if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
				flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
				if flowed > 0:
					e.cap -= flowed
					self._graph[e.to][e.rev].cap += flowed
					return flowed
			self._iter[cur_vertex] += 1
		return 0

	def solve(self, source, sink):
		flow = 0
		while True:
			self.bfs(source)
			if self._level[sink] < 0:
				return flow
			self._iter = [0] * self._node
			while True:
				f = self.dfs(source, sink, self._inf)
				if f == 0:
					break
				flow += f

class BipartiteMatching:

	def __init__(self, size1, size2):
		(self._u_size, self._v_size) = (size1, size2)
		self.mf = MaxFlow(self._u_size + self._v_size + 2, min(self._u_size, self._v_size))
		for i in range(self._u_size):
			self.mf.add_edge(0, i + 1, 1)
		for i in range(self._v_size):
			self.mf.add_edge(self._u_size + i + 1, self._u_size + self._v_size + 1, 1)

	def add_edge(self, from_, to):
		self.mf.add_edge(from_ + 1, to + self._u_size + 1, 1)

	def solve(self):
		return self.mf.solve(0, self._u_size + self._v_size + 1)
(x, y, m) = map(int, sys.stdin.readline().split())
bm = BipartiteMatching(x, y)
for _ in range(m):
	(u, v) = map(int, sys.stdin.readline().split())
	bm.add_edge(u, v)
print(bm.solve())


class Dinic:

	def __init__(self, len_X, len_Y):
		(self.len_X, self.len_Y) = (len_X, len_Y)
		self.edges = [[] for _ in range(len_X)]
		self.matched = [-1] * len_Y
		self.visited = set()

	def add_edge(self, x, y):
		self.edges[x].append(y)

	def dfs(self, x):
		for next_x in self.edges[x]:
			if next_x in self.visited:
				continue
			self.visited.add(next_x)
			if self.matched[next_x] == -1 or self.dfs(self.matched[next_x]):
				self.matched[next_x] = x
				return True
		return False

	def solve(self):
		res = 0
		for x in range(self.len_X):
			self.visited = set()
			res += self.dfs(x)
		return res
(len_X, len_Y, E) = map(int, input().split())
dinic = Dinic(len_X, len_Y)
for _ in range(E):
	(x, y) = map(int, input().split())
	dinic.add_edge(x, y)
print(dinic.solve())


class Node:

	def __init__(self):
		self.edge = []
		self.level = None
		self.par = None
		self.cap = 10 ** 18

class Edge:

	def __init__(self, to, cap, rev=None):
		self.to = to
		self.cap = cap
		self.rev = rev
from collections import deque

class BipartiteMatching:

	def __init__(self, n, m):
		self.n = n
		self.m = m
		self.inf = 10 ** 18
		self.source = Node()
		self.sink = Node()
		self.lt = [Node() for _ in range(n)]
		self.rt = [Node() for _ in range(m)]
		for i in range(n):
			edge = Edge(self.lt[i], 1)
			rev = Edge(self.source, 0)
			(edge.rev, rev.rev) = (rev, edge)
			self.source.edge.append(edge)
			self.lt[i].edge.append(rev)
		for i in range(m):
			edge = Edge(self.sink, 1)
			rev = Edge(self.rt[i], 0)
			(edge.rev, rev.rev) = (rev, edge)
			self.rt[i].edge.append(edge)
			self.sink.edge.append(rev)

	def add(self, x, y):
		lt = self.lt[x]
		rt = self.rt[y]
		edge = Edge(rt, 1)
		rev = Edge(lt, 0)
		(edge.rev, rev.rev) = (rev, edge)
		lt.edge.append(edge)
		rt.edge.append(rev)

	def maximum_matching(self):
		flow = 0
		while True:
			queue = deque([self.source])
			self.source.level = 0
			self.sink.level = None
			for i in range(self.n):
				self.lt[i].level = None
			for i in range(self.m):
				self.rt[i].level = None
			while queue:
				node = queue.popleft()
				for edge in node.edge:
					to = edge.to
					if edge.cap and to.level is None:
						to.level = node.level + 1
						queue.append(to)
			if self.sink.level is None:
				break
			stack = [self.source]
			self.source.par = None
			self.sink.par = None
			for i in range(self.n):
				self.lt[i].par = None
			for i in range(self.m):
				self.rt[i].par = None
			while stack:
				node = stack.pop()
				if node is self.sink:
					break
				for edge in node.edge:
					to = edge.to
					if edge.cap and node.level < to.level:
						to.par = edge.rev
						stack.append(to)
			node = self.sink
			delta = node.cap
			while node is not self.source:
				node.par.cap = 1
				node.par.rev.cap = 0
				node = node.par.to
			flow += 1
		return flow
import sys
input = sys.stdin.readline
(N, M, E) = map(int, input().split())
bm = BipartiteMatching(N, M)
for _ in range(E):
	(x, y) = map(int, input().split())
	bm.add(x, y)
print(bm.maximum_matching())


import sys, collections
sys.setrecursionlimit(100000)
INF = float('inf')
(X, Y, E) = map(int, sys.stdin.readline().split())
xy = tuple((tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(E)))
V = X + Y + 2
uvc = [[x + 1, y + X + 1, 1] for (x, y) in xy]
for i in range(X):
	uvc.append([0, i + 1, 1])
for i in range(Y):
	uvc.append([X + i + 1, V - 1, 1])
G = {i: {} for i in range(V)}
mG = {i: {} for i in range(V)}
for (u, v, c) in uvc:
	G[u][v] = c
	G[v][u] = 0
	mG[u][v] = 0
	mG[v][u] = 0

def dfs(current, flow):
	if current == V - 1:
		return flow
	visited.add(current)
	for (nex, nex_c) in G[current].items():
		if not nex in visited and nex_c != 0:
			f = dfs(nex, min(flow, nex_c))
			if f != 0:
				mG[current][nex] = mG[current][nex] + f
				G[current][nex] = G[current][nex] - f
				G[nex][current] = G[nex][current] + f
				return f
	return 0
visited = set()
while dfs(0, INF) != 0:
	visited = set()
	pass
print(sum(mG[0].values()))


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].add(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if not visited[adj] and adj in adj_table[current]:
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [set() for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


import sys
from queue import deque
sys.setrecursionlimit(200000)

def hierarchize(source):
	global hierarchy
	hierarchy = [-1] * n
	queue = deque([(0, source)])
	while queue:
		(h, v) = queue.popleft()
		if hierarchy[v] != -1:
			continue
		hierarchy[v] = h
		if v == sink:
			return True
		queue.extend(((h + 1, target) for (remain, target, _) in edges[v] if hierarchy[target] == -1 and remain))
	return False

def augment(v, limit):
	if v == sink:
		return limit
	res = 0
	for e in edges[v]:
		(remain, target, idx) = e
		if remain == 0 or hierarchy[v] >= hierarchy[target]:
			continue
		aug = augment(target, min(limit, remain))
		e[0] -= aug
		edges[target][idx][0] += aug
		res += aug
		limit -= aug
		if not limit:
			break
	return res
(xn, yn, e) = map(int, input().split())
n = xn + yn + 2
sink = n - 1
edges = [[] for _ in range(n)]
hierarchy = [-1] * n
for x in range(xn):
	xi = x + 1
	edges[0].append([1, xi, 0])
	edges[xi].append([0, 0, x])
for y in range(yn):
	yi = xn + y + 1
	edges[yi].append([1, sink, y])
	edges[sink].append([0, yi, 0])
for _ in range(e):
	(x, y) = map(int, input().split())
	(xi, yi) = (x + 1, xn + y + 1)
	(ex, ey) = (edges[xi], edges[yi])
	(lx, ly) = (len(ex), len(ey))
	ex.append([1, yi, ly])
	ey.append([0, xi, lx])
res = 0
while hierarchize(0):
	res += augment(0, 100)
print(res)


import sys
from collections import deque
sys.setrecursionlimit(200000)

class Dinic:

	def __init__(self, v, inf=10 ** 10):
		self.v = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [-1] * v
		self.ite = [0] * v

	def add_edge(self, fr, to, cap):
		self.G[fr].append([to, cap, len(self.G[to])])
		self.G[to].append([fr, 0, len(self.G[fr]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.v
		self.level[s] = 0
		Q = deque()
		Q.append(s)
		while Q:
			v = Q.popleft()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					Q.append(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.ite[v], len(self.G[v])):
			self.ite[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.ite = [0] * self.v
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
(x, y, e) = map(int, input().split())
D = Dinic(x + y + 2)
for _ in range(e):
	(u, w) = map(int, input().split())
	D.add_edge(u, w + x, 1)
for i in range(x + y):
	if i < x:
		D.add_edge(x + y, i, 1)
	else:
		D.add_edge(i, x + y + 1, 1)
ans = D.max_flow(x + y, x + y + 1)
print(ans)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

class BipartiteMatching:

	def __init__(self, N, M):
		self.N = N
		self.M = M
		self.pairA = [-1] * N
		self.pairB = [-1] * M
		self.edge = [[] for _ in range(N)]
		self.was = [0] * N
		self.iter = 0

	def add(self, s, t):
		self.edge[s].append(t)

	def _DFS(self, s):
		self.was[s] = self.iter
		for t in self.edge[s]:
			if self.pairB[t] == -1:
				self.pairA[s] = t
				self.pairB[t] = s
				return True
		for t in self.edge[s]:
			if self.was[self.pairB[t]] != self.iter and self._DFS(self.pairB[t]):
				self.pairA[s] = t
				self.pairB[t] = s
				return True
		return False

	def solve(self):
		res = 0
		while True:
			self.iter += 1
			found = 0
			for i in range(self.N):
				if self.pairA[i] == -1 and self._DFS(i):
					found += 1
			if not found:
				break
			res += found
		return res
(X, Y, E) = map(int, input().split())
match = BipartiteMatching(X, Y)
for _ in range(E):
	(x, y) = map(int, input().split())
	match.add(x, y)
ans = match.solve()
print(ans)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:

	def __init__(self, v, inf=10 ** 10):
		self.v = v
		self.inf = inf
		self.G = [[] for _ in range(v)]
		self.level = [-1] * v
		self.ite = [0] * v

	def add_edge(self, fr, to, cap):
		self.G[fr].append([to, cap, len(self.G[to])])
		self.G[to].append([fr, 0, len(self.G[fr]) - 1])

	def bfs(self, s):
		self.level = [-1] * self.v
		self.level[s] = 0
		Q = deque()
		Q.append(s)
		while Q:
			v = Q.popleft()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					Q.append(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.ite[v], len(self.G[v])):
			self.ite[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.ite = [0] * self.v
			f = self.dfs(s, t, self.inf)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.inf)
(X, Y, E) = MAP()
D = Dinic(X + Y + 2)
s = X + Y
t = X + Y + 1
for i in range(X):
	D.add_edge(s, i, 1)
for i in range(Y):
	D.add_edge(X + i, t, 1)
for _ in range(E):
	(x, y) = MAP()
	D.add_edge(x, X + y, 1)
print(D.max_flow(s, t))


from sys import stdin
from collections import defaultdict
readline = stdin.readline

def main():
	(x, y, e) = map(int, readline().split())
	g = defaultdict(list)
	residual = [[0] * (x + y + 2) for _ in range(x + y + 2)]
	(source, sink) = (x + y, x + y + 1)
	for xi in range(x):
		g[source].append(xi)
		residual[source][xi] = 1
	for yi in range(x, x + y):
		g[yi].append(sink)
		residual[yi][sink] = 1
	for _ in range(e):
		(s, t) = map(int, readline().split())
		t += x
		g[s].append(t)
		g[t].append(s)
		residual[s][t] = 1
	while True:
		(route, flow) = search(g, residual, source, sink)
		if not route:
			break
		for (s, t) in zip(route, route[1:]):
			residual[s][t] -= flow
			residual[t][s] += flow
	print(sum(residual[sink]))

def search(g, residual, source, sink):
	dfs_stack = [(source, None, float('inf'))]
	route = [None]
	visited = set()
	while dfs_stack:
		(u, prev, flow) = dfs_stack.pop()
		while route[-1] != prev:
			route.pop()
		route.append(u)
		visited |= {u}
		if u == sink:
			return (route[1:], flow)
		for v in g[u]:
			if v not in visited and 0 < residual[u][v]:
				dfs_stack.append((v, u, min(residual[u][v], flow)))
	return ([], 0)
main()


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if adj in adj_table[current] and (not visited[adj]):
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * v_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
v_num = x_num + y_num
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


class BipartiteMatching:

	def __init__(self, V):
		self.V = V
		self.G = [[] for _ in range(V)]

	def add_edge(self, u, v):
		self.G[u].append(v)
		self.G[v].append(u)

	def dfs(self, u):
		self.used[u] = True
		for v in self.G[u]:
			w = self.match[v]
			if w < 0 or (not self.used[w] and self.dfs(w)):
				self.match[u] = v
				self.match[v] = u
				return True
		return False

	def bipartite_matching(self):
		res = 0
		self.match = [-1] * self.V
		for v in range(self.V):
			if self.match[v] == -1:
				self.used = [False] * self.V
				if self.dfs(v):
					res += 1
		return res
(X, Y, E) = map(int, input().split())
bm = BipartiteMatching(X + Y)
for _ in range(E):
	(x, y) = map(int, input().split())
	bm.add_edge(x, X + y)
print(bm.bipartite_matching())


def dfs(u):
	for v in range(nv):
		if adj[u][v] and (not visited[v]):
			visited[v] = True
			if matches[v] is None or dfs(matches[v]):
				matches[v] = u
				return True
	return False
(nu, nv, ne) = map(int, input().split(' '))
adj = [[False] * nv for _ in range(nu)]
matches = [None] * nv
count = 0
for _ in range(ne):
	(s, t) = map(int, input().split(' '))
	adj[s][t] = True
for u in range(nu):
	visited = [False] * nv
	if dfs(u):
		count += 1
print(count)


def outer(x, match, phi):
	if match[x] == x or phi[match[x]] != match[x]:
		return True
	return False

def inner(x, match, phi):
	if match[x] != x and phi[match[x]] == match[x] and (phi[x] != x):
		return True
	return False

def F(x, match, phi):
	if match[x] != x and phi[match[x]] == match[x] and (phi[x] == x):
		return True
	return False

def disjoint(x, y, V, phi, match):
	usedx = [False] * V
	prex = match[x]
	while not (usedx[x] and usedx[prex]):
		usedx[prex] = True
		usedx[x] = True
		x = phi[prex]
		prex = match[x]
	usedy = [False] * V
	prey = match[y]
	while not (usedy[y] and usedy[prey]):
		usedy[y] = True
		usedy[prey] = True
		if usedx[y] or usedx[prey]:
			return False
		prey = match[y]
		y = phi[prey]
	return True

def shrink(x, y, match, rho, phi, V):
	r = firstvertex(x, y, match, phi, rho, V)
	v = match[x]
	if x != r and x != v:
		while True:
			if rho[phi[v]] != r:
				phi[phi[v]] = v
			if phi[v] == r or match[phi[v]] == r:
				break
			v = match[phi[v]]
	v = match[y]
	if y != r and y != v:
		while True:
			if rho[phi[v]] != r:
				phi[phi[v]] = v
			if phi[v] == r or match[phi[v]] == r:
				break
			v = match[phi[v]]
	if rho[x] != r:
		phi[x] = y
	if rho[y] != r:
		phi[y] = x
	used = [False] * V
	used[r] = True
	while x != r or y != r:
		used[x] = True
		used[y] = True
		if x != r:
			x = match[x]
		if y != r:
			y = match[y]
		used[x] = True
		used[y] = True
		if x != r:
			x = phi[x]
		if y != r:
			y = phi[y]
	for i in range(V):
		if used[rho[i]]:
			rho[i] = r

def firstvertex(x, y, match, phi, rho, V):
	usedx = [False] * V
	usedy = [False] * V
	flag = True
	while True:
		if usedy[x] and rho[x] == x:
			return x
		usedx[x] = True
		if usedx[y] and rho[y] == y:
			return y
		usedy[y] = True
		if flag:
			x = match[x]
			y = match[y]
			flag = False
		else:
			x = phi[x]
			y = phi[y]
			flag = True

def augment(x, y, match, phi, V):
	v = match[x]
	used = [False] * V
	used[x] = True
	while not used[v]:
		used[v] = True
		used[phi[v]] = True
		tmp = match[phi[v]]
		match[phi[v]] = v
		match[v] = phi[v]
		v = tmp
	v = match[y]
	used = [False] * V
	used[y] = True
	while not used[v]:
		used[v] = True
		used[phi[v]] = True
		tmp = match[phi[v]]
		match[phi[v]] = v
		match[v] = phi[v]
		v = tmp
	match[x] = y
	match[y] = x

def Edmonds(graph, V):
	match = [i for i in range(V)]
	phi = [i for i in range(V)]
	rho = [i for i in range(V)]
	scanned = [False] * V
	while True:
		flag = True
		for i in range(V):
			if not scanned[i] and outer(i, match, phi):
				x = i
				flag = False
				break
		if flag:
			break
		for y in graph[x]:
			if F(y, match, phi):
				phi[y] = x
				continue
			if not (outer(y, match, phi) and rho[y] != rho[x]):
				continue
			if disjoint(x, y, V, phi, match):
				augment(x, y, match, phi, V)
				scanned = [False] * V
				rho = [i for i in range(V)]
				phi = [i for i in range(V)]
				flag = True
				break
			shrink(x, y, match, rho, phi, V)
		if not flag:
			scanned[x] = True
	cnt = 0
	for i in range(V):
		if match[i] != i:
			cnt += 1
	return int(cnt / 2)
(x, y, e) = list(map(int, input().split()))
v = x + y
graph = [[] for _ in range(v)]
for i in range(e):
	(tmp1, tmp2) = list(map(int, input().split()))
	tmp2 += x
	graph[tmp1].append(tmp2)
	graph[tmp2].append(tmp1)
cnt = Edmonds(graph, v)
print(cnt)


import sys

def dfs(current, matching, visited):
	for target in range(y_num):
		if not visited[target] and target in adj_table[current]:
			visited[target] = True
			if matching[target] == -1 or dfs(matching[target], matching, visited):
				matching[target] = current
				return True
	return False

def mbm():
	res = 0
	matching = [-1] * y_num
	for source in range(x_num):
		visited = [False] * y_num
		if dfs(source, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
adj_table = tuple((set() for _ in range(x_num)))
for edge in edges:
	(vx, vy) = map(int, edge)
	adj_table[vx].add(vy)
print(mbm())


import sys

def generate_adj_table(_edges):
	for edge in _edges:
		(vx, vy) = map(int, edge)
		init_adj_table[vx].append(vy)
	return init_adj_table

def graph_dfs(current, matching, visited):
	for adj in range(y_num):
		if adj in adj_table[current] and (not visited[adj]):
			visited[adj] = True
			if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
				matching[adj] = current
				return True
	return False

def mbm():
	matching = [-1] * y_num
	res = 0
	for v in range(x_num):
		visited = [False] * y_num
		if graph_dfs(v, matching, visited):
			res += 1
	return res
_input = sys.stdin.readlines()
(x_num, y_num, e_num) = map(int, _input[0].split())
edges = map(lambda x: x.split(), _input[1:])
init_adj_table = [[] for _ in range(x_num)]
adj_table = generate_adj_table(edges)
print(mbm())


def dfs(v, visited):
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or dfs(matched[u], visited):
			matched[u] = v
			return True
	return False
(xn, yn, e) = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn
for _ in range(e):
	(x, y) = map(int, input().split())
	edges[x].add(y)
print(sum((dfs(s, set()) for s in range(xn))))


from collections import deque

class Bipartite_Matching:

	def __init__(self, input_graph: list):
		n = len(input_graph)
		self.INF = float('inf')
		visited = [-1] * n
		for i in range(n):
			if visited[i] >= 0:
				continue
			visited[i] = 0
			q = deque([i])
			while q:
				_from = q.pop()
				for to in input_graph[_from]:
					if visited[to] >= 0:
						continue
					visited[to] = visited[_from] ^ 1
					q.append(to)
		self.s = n
		self.t = n + 1
		self.n = n + 2
		self.graph = [[] for i in range(self.n)]
		used = set([])
		for pos1 in range(n):
			if visited[pos1] == 0:
				self.add_edge(self.s, pos1)
			else:
				self.add_edge(pos1, self.t)
			for pos2 in input_graph[pos1]:
				if (min(pos1, pos2), max(pos1, pos2)) in used:
					continue
				used.add((min(pos1, pos2), max(pos1, pos2)))
				if visited[pos1] == 0:
					self.add_edge(pos1, pos2)
				else:
					self.add_edge(pos2, pos1)

	def add_edge(self, _from: int, to: int):
		forward = [to, 1, None]
		forward[2] = backward = [_from, 0, forward]
		self.graph[_from].append(forward)
		self.graph[to].append(backward)

	def bfs(self, s: int, t: int):
		self.level = [-1] * self.n
		q = deque([s])
		self.level[s] = 0
		while q:
			_from = q.popleft()
			for (to, capacity, _) in self.graph[_from]:
				if capacity > 0 and self.level[to] < 0:
					self.level[to] = self.level[_from] + 1
					q.append(to)

	def dfs(self, _from: int, t: int, f: int) -> int:
		if _from == t:
			return f
		for edge in self.itr[_from]:
			(to, capacity, reverse_edge) = edge
			if capacity > 0 and self.level[_from] < self.level[to]:
				d = self.dfs(to, t, min(f, capacity))
				if d > 0:
					edge[1] -= d
					reverse_edge[1] += d
					return d
		return 0

	def max_flow(self):
		flow = 0
		while True:
			self.bfs(self.s, self.t)
			if self.level[self.t] < 0:
				break
			self.itr = list(map(iter, self.graph))
			f = self.dfs(self.s, self.t, self.INF)
			while f > 0:
				flow += f
				f = self.dfs(self.s, self.t, self.INF)
		return flow
(x, y, e) = map(int, input().split())
graph = [[] for i in range(x + y)]
for i in range(e):
	(tmp_x, tmp_y) = map(int, input().split())
	graph[tmp_x].append(tmp_y + x)
	graph[tmp_y + x].append(tmp_x)
mb = Bipartite_Matching(graph)
print(mb.max_flow())


from typing import Set

def dfs(s: int) -> bool:
	return _dfs(s, set())

def _dfs(v: int, visited: Set[int]) -> bool:
	for u in edges[v]:
		if u in visited:
			continue
		visited.add(u)
		if matched[u] == -1 or _dfs(matched[u], visited):
			matched[u] = v
			return True
	return False
(xn, yn, e) = map(lambda x: int(x), input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn
for _ in range(e):
	(x, y) = map(lambda x: int(x), input().split())
	edges[x].add(y)
print(sum(map(dfs, range(xn))))


from collections import deque

class Dinic(object):
	__slots__ = ['inf', 'v_count', 'edges', 'iter', 'level']

	def __init__(self, v_count: int, edges: list):
		self.inf = 10 ** 9
		self.v_count = v_count
		self.edges = [[] for _ in [0] * v_count]
		self.iter = [0] * v_count
		self.level = None
		self._create_graph(edges)

	def _create_graph(self, _edges):
		edges = self.edges
		for (origin, dest, cap) in _edges:
			edges[origin].append([dest, cap, len(edges[dest])])
			edges[dest].append([origin, 0, len(edges[origin]) - 1])

	def solve(self, source: int, sink: int):
		max_flow = 0
		while True:
			self.bfs(source)
			if self.level[sink] < 0:
				return max_flow
			self.iter = [0] * self.v_count
			flow = self.dfs(source, sink, self.inf)
			while flow > 0:
				max_flow += flow
				flow = self.dfs(source, sink, self.inf)

	def bfs(self, source: int):
		(level, edges) = ([-1] * self.v_count, self.edges)
		level[source] = 0
		dq = deque([source])
		(popleft, append) = (dq.popleft, dq.append)
		while dq:
			v = popleft()
			for (dest, cap, _rev) in edges[v]:
				if cap > 0 > level[dest]:
					level[dest] = level[v] + 1
					append(dest)
		self.level = level

	def dfs(self, source: int, sink: int, flow: int) -> int:
		if source == sink:
			return flow
		while self.iter[source] < len(self.edges[source]):
			(dest, cap, rev) = edge = self.edges[source][self.iter[source]]
			if cap > 0 and self.level[source] < self.level[dest]:
				flowed = self.dfs(dest, sink, flow if flow < cap else cap)
				if flowed > 0:
					edge[1] -= flowed
					self.edges[dest][rev][1] += flowed
					return flowed
			self.iter[source] += 1
		return 0
import sys
(X, Y, E) = map(int, input().split())
(source, sink) = (X + Y, X + Y + 1)
edges = [(source, i, 1) for i in range(X)] + [(X + i, sink, 1) for i in range(Y)]
append = edges.append
for (x, y) in (map(int, l.split()) for l in sys.stdin):
	append((x, X + y, 1))
dinic = Dinic(X + Y + 2, edges)
print(dinic.solve(source, sink))