MATCHING - Fast Maximum Matching


FJ has N (1 ≤ N ≤ 50,000) cows and M (1 ≤ M ≤ 50,000) bulls. Given a list of P (1 ≤ P ≤ 150,000) potential matches between a cow and a bull, compute the greatest number of pairs that can be matched. Of course, a cow can be matched to at most one bull, and vice versa.

Input

The first line contains three integers, N, M, and P. Each of the next P lines contains two integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ M), denoting that cow A can be matched with bull B.

Output

Print a single integer that is the maximum number of pairs that can be obtained.

Example

Input:
5 4 6
5 2
1 2
4 3
3 1
2 2
4 4

Output:
3

Cow 1 can be matched to bull 2, cow 3 to bull 1, and cow 4 to bull 3.

Note: see also http://www.spoj.com/problems/FASTFLOW/.


hide comments
Lucas Daniel: 2012-06-17 03:46:14

How is it possible to get accepted in the problem Fast Maximum Flow and wrong answer here? I'm using push-relabel with global relabel heuristic.

熊怀东: 2012-06-03 08:40:40

@changiz
I suggest reading flowing paper ,it describe a nice and easy algorithm (I like it)
http://www.duet.ac.bd/journal/5.pdf

This algorithm is easy to understand. I tried, but exceeded the time limit. How can we implement the algorithm efficiently?

Adi Chris Dpp Bangun: 2012-05-03 04:57:16

can anyone give me more tescase..i got WA, i have used HK Algorithm..

changiz: 2011-08-15 18:08:13

I suggest reading flowing paper ,it describe a nice and easy algorithm (I like it)
http://www.duet.ac.bd/journal/5.pdf

hjss06: 2011-04-01 13:13:51

We must use HK algorithm or one more fast!

Brian Bi: 2010-01-12 05:37:43

Are there duplicate pairs in input?


Added by:Neal Wu
Date:2009-04-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO