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
lukaszpolska: 2023-10-14 23:01:39

Can somone explain why Edmond karp with 2 additional vertices dont work here (wa on test 7)?

treenipples: 2021-05-23 12:34:10

Kuhn's BPM passes if you shuffle the graph

Last edit: 2021-05-23 20:02:16
nemesys: 2020-10-09 04:59:49

Got TLE with Dinic

emej: 2020-03-15 17:24:01

Edmond karp barely passes

threat_: 2019-10-16 02:42:51

Edmond Karp passes

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


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