## 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
 < Previous 1 2 3 Next > msh2481: 2018-10-02 07:04:04 Fast Kuhn get AC) joqsan_77: 2018-08-22 16:54:52 A well-written Dinic's algorithm passes. vincecao: 2017-12-05 12:50:13 always tle made me try every possible way to reduce the time cost, however it resulted in the bug in HK causing the dead loop... simp: 2017-11-21 04:06:56 Kuhn will not pass, you should use algorithm Hopcroft-Karp. br4in1: 2017-11-20 16:12:24 simple dp 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)

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