Maximum Bipartite Matching

Given a bipartite graph with left vertices numbered from 1 to n and right vertices numbered from 1 to m, and with a total of e edges, determine the maximum matching of the graph.

An edge connects a vertex from the left part to a vertex from the right part. A matching is a set of edges such that no two edges share a common vertex. Formally, if \(n\) denotes the number of left vertices, \(m\) the number of right vertices, and \(e\) the number of edges, you are to compute the maximum number of edges in a matching.

inputFormat

The input consists of multiple lines. The first line contains three integers: \(n\), \(m\), and \(e\), representing the number of left vertices, the number of right vertices, and the total number of edges, respectively.

Each of the following \(e\) lines contains two integers \(u\) and \(v\), where \(u\) (with \(1 \leq u \leq n\)) is a vertex in the left part and \(v\) (with \(1 \leq v \leq m\)) is a vertex in the right part that is connected to \(u\) by an edge.

outputFormat

Output a single integer representing the maximum number of edges that can form a matching in the given bipartite graph.

sample

2 2 2
1 1
2 2

2