NGUỒN: CONTEST PRACTICE VNOI20 (WEEK 2 - T11/2019)
Cho đồ thị gồm đỉnh đánh số từ đến , đỉnh thứ có màu . Người ta thêm lần lượt cạnh vô hướng vào đồ thị, cạnh thứ nối hai đỉnh .
Yêu cầu: Sau mỗi bước thêm cạnh, đếm số cặp đỉnh cùng màu mà từ có thể đến qua các cạnh của đồ thị .
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên dương
- Dòng thứ hai chứa số nguyên dương
- dòng tiếp, dòng thứ chứa hai số nguyên dương
Dữ liệu ra:
- Gồm dòng, mỗi dòng là số cặp cùng màu mà từ có thể đến được qua các cạnh của đồ thị.
Ví dụ:
Dữ liệu vào:
4 4
1 2 1 2
1 2
3 4
1 3
2 3
Dữ liệu ra:
Giới hạn:
- số test có
- số test còn lại không có ràng buộc gì thêm
