Cho
một bảng ô vuông gồm n dòng và m cột. Các dòng được đánh số từ 1 đến n, các cột được đánh số từ 1 đên m. Ô nằm ở dòng i và cột j được gọi là ô
(i, j). Có k ô màu đen trên bảng, ô đen thứ i nằm ở vị trí (xi,
yi). Các ô còn lại trong bảng đều có màu trắng.
Bạn có thể thực hiện một trong hai
loại thao tác sau (mỗi thao tác có thể được thực hiện nhiều lần hoặc không lần
nào).
- Chọn một dòng chỉ gồm các ô màu
trắng, và xóa dòng đó khỏi bảng.
- Chọn một cột chỉ gồm các ô màu
trắng, và xóa cột đó khỏi bảng.
Hãy tìm cách thực hiện các loại thao
tác trên, sao cho số ô còn lại trong bảng là nhỏ nhất có thể.
Dữ liệu vào:
- Dòng đầu tiên gồm ba số nguyên n, m, k (1 ≤ n, m, k ≤ 105) – số dòng, số cột của bảng và số ô đen.
- k dòng tiếp theo, dòng thứ i
gồm hai số nguyên xi, yi
(1 ≤ xi ≤ n, 1 ≤ yi ≤ m) – vị trí của ô đen thứ
i. Dữ liệu vào đảm bảo không có hai ô
đen nào ở cùng vị trí.
Dữ
liệu ra: In ra số ô còn lại nhỏ nhất có thể sau khi thực hiện hai loại thao tác
trên.
Ví dụ:
|
Input |
Output |
|
3
4 3 2
1 2
4 3
3 |
6 |
|
4
4 4 2
1 3
4 4
1 4
4 |
6 |
Đăng nhận xét