FMATCH - Fast Maximum Matching

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/.


Được gửi lên bởi:Race with time
Ngày:2009-04-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Neal Wu - SPOJ

hide comments
2020-10-26 04:43:55
Comment bên dưới là của Thái Bá Hưng A2K48,không phải của Thanh Tuyển
2020-10-26 04:40:35
Hom nay Thanh Tuyen A2K48 hoc cap ghep
Tuong ko kho hoa ra kho khong tuong :D
2017-03-20 19:06:32
cạp ghép mà n m thế kia ai chơi nhỉ ??
2015-06-11 05:14:36 Nguyen Tri Nhan
Leave a Comment
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.