Ghép Cặp Hoàn Hảo
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề 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
YESnếu tồn tại cặp ghép hoàn hảo, ngược lại in raNO.
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
Community Discussion