Ghép Đôi Trực Tuyến
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một đồ thị hai phía ban đầu chưa có cạnh nào, gồm $N$ đỉnh phía trái và $M$ đỉnh phía phải.
Có $Q$ truy vấn trực tuyến đến lần lượt. Mỗi truy vấn thêm một cạnh $(u, v)$ vào đồ thị. Ngay sau mỗi truy vấn, hãy in ra kích thước cặp ghép cực đại hiện tại của đồ thị.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 \le N, M \le 2000$, $1 \le Q \le 10\,000$).
- $Q$ 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
- Gồm $Q$ dòng, dòng thứ $i$ là kích thước cặp ghép cực đại sau khi thêm cạnh thứ $i$.
Ví dụ
Input
3 3 5
1 1
2 1
1 2
3 2
2 3
Output
1
1
2
2
3
Giải thích
- Sau $(1, 1)$: ghép được $1$.
- Sau $(2, 1)$: vẫn chỉ ghép được $1$.
- Sau $(1, 2)$: ghép $(1, 2)$ và $(2, 1)$, kích thước là $2$.
- Sau $(3, 2)$: vẫn là $2$.
- Sau $(2, 3)$: ghép $(1, 2)$, $(2, 3)$? Không, $(1,1)$, $(3,2)$, $(2,3)$, kích thước là $3$.
Giới hạn
- $1 \le N, M \le 2000$
- $1 \le Q \le 10\,000$
- Thời gian: 3 giây
- Bộ nhớ: 256 MB
Community Discussion