FMATCH - Fast Maximum Matching

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/fmatch


FJ có N (1 ≤ N ≤ 50,000) cô bò và M (1 ≤ M ≤ 50,000) chú bò. Cho danh sách P (1 ≤ P ≤ 150,000) khả năng ghép đôi giữa các cô bò và chú bò, hãy tính số cặp lớn nhất có thể ghép được. Tất nhiên, một cô bò có thể ghép với tối đa là một chú bò và ngược lại.

Input

Dòng đầu tiên chứa 3 số nguyên, N, M, và P. Mỗi dòng trong số P dòng tiếp theo chứa 2 số nguyên A (1 ≤ A ≤ N) và B (1 ≤ B ≤ M), thể hiện việc cô bò A có thể ghép được với chú bò B.

Output

In ra một số nguyên thể hiện số cặp lớn nhất có thể đạt được.

Example

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


Output:
3

Cô bò 1 có thể được ghép với chú bò 2, cô bò 3 với chú bò 1, và cô bò 4 với chú bò 3.

Bài gốc: https://www.spoj.com/problems/MATCHING/.



Added by:Race with time
Date:2009-04-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Neal Wu - SPOJ