Fast Maximum Matching

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Neal Wu - SPOJ
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

FJ có ~N~ ~(1 \leq N \leq 50~, ~000)~ cô bò và ~M~ ~(1 \leq M \leq 50~, ~000)~ chú bò.

Cho danh sách ~P~ ~(1 \leq P \leq 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 \leq A \leq N)~ và ~B~ ~(1 \leq B \leq 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.

Sample Input

5 4 6
5 2
1 2
4 3
3 1
2 2
4 4

Sample Output

3

Note

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.