Fast Maximum Matching

Điểm: 0,40 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Neal Wu - SPOJ

Dạng bài

Ngôn ngữ cho phép

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

Copy

Sample Output

Copy

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

Bình luận

Hãy đọc nội quy trước khi bình luận.

-9

sitingfake đã bình luận 2:39:56 sa, 07/10/2024

xin down vote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.