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
andre schurrle:
20150606 13:43:58
Last edit: 20150615 05:17:33 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150529 00:45:06
From TLE to top 10 fastest _


Rishab Kalra:
20140117 16:50:02
getting wrong answer at 7th test case...any special case?


abdelkarim:
20130707 06:34:32
@changiz


ByambadorjP:
20120723 06:35:13
Hi guys. I solved this problem in runtime nearly 3. But many people solved this problem better than my runtime. Please send me a better solution to my email. byambadorjp@gmail.com please!!! 

Lucas Daniel:
20120617 03:46:14
How is it possible to get accepted in the problem Fast Maximum Flow and wrong answer here? I'm using pushrelabel with global relabel heuristic. 

熊怀东:
20120603 08:40:40
@changiz


Adi Chris Dpp Bangun:
20120503 04:57:16
can anyone give me more tescase..i got WA, i have used HK Algorithm.. 

changiz:
20110815 18:08:13
I suggest reading flowing paper ,it describe a nice and easy algorithm (I like it)


hjss06:
20110401 13:13:51
We must use HK algorithm or one more fast! 
Added by:  Neal Wu 
Date:  20090412 
Time limit:  0.400s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 