Ghép Cặp Hoàn Hảo

Buổi 49 — Matching (Hopcroft-Karp)
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions

Đề bài

Trong một buổi vũ hội, có $N$ bạn nam (đánh số từ $1$ đến $N$) và $M$ bạn nữ (đánh số từ $1$ đến $M$). Có $E$ cặp $(u, v)$ cho biết bạn nam $u$ và bạn nữ $v$ sẵn sàng khiêu vũ cùng nhau.

Ban tổ chức muốn ghép tất cả mọi người thành các cặp đôi sao cho mỗi bạn nam ghép với đúng một bạn nữ và mỗi bạn nữ ghép với đúng một bạn nam (cặp ghép hoàn hảo). Hãy kiểm tra xem điều này có thực hiện được không.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, M, E$ ($1 \le N, M \le 50\,000$, $0 \le E \le 150\,000$).
  • $E$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u \le N$, $1 \le v \le M$).

Dữ liệu ra

  • In ra YES nếu tồn tại cặp ghép hoàn hảo, ngược lại in ra NO.

Ví dụ

Input
3 3 5
1 1
1 2
2 2
2 3
3 1
Output
YES

Giải thích

Có thể ghép $(1, 2)$, $(2, 3)$, $(3, 1)$, tất cả 6 người đều có cặp.

Giới hạn

  • $1 \le N, M \le 50\,000$
  • $0 \le E \le 150\,000$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved