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
Luis Manuel Díaz Barón: 2017-05-29 17:34:09

Kuhn -> TLE .... WHY???? Has anyone got AC using Kuhn ??

hamzaziadeh: 2016-10-16 21:07:37

ac in 1 go, easy problem for beginners.

Jeenu Grover: 2016-07-18 09:20:07

@ufrnmaratona Did you find out why are you getting a wrong answer. I have done the same thing and wrong answer. I f possible please give a test case.

Ashraful Islam: 2016-02-16 22:05:56

please some one help me,i use kuhn's algorithm and get TLE.
what should i do to make it accepted??
this is my sub mission=>http://www.spoj.com/status/MATCHING,mahim007/

dacin21: 2016-02-13 15:43:34

Wait, why does lowest label push relabel pass while highest label is to slow?? (Using a pretty optimized implementation)

andre schurrle: 2015-06-06 13:43:58

Last edit: 2015-06-15 05:17:33
(Tjandra Satria Gunawan)(曾毅昆): 2015-05-29 00:45:06

From TLE to top 10 fastest -_-
Definitely overkill optimization ;-)

Rishab Kalra: 2014-01-17 16:50:02

getting wrong answer at 7th test case...any special case?

abdelkarim: 2013-07-07 06:34:32

@changiz
it's not allowed to post any solution here !
read notes carefully please.
"1. Don't post any source code here."

ByambadorjP: 2012-07-23 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!!!


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