Cho một đồ thị vô hướng tên là Dark gồm đỉnh và hai loại cạnh: cạnh chính và cạnh phụ. Đồ thị có cạnh chính, và các cạnh này tạo thành một cây nối tất cả đỉnh. Ngoài ra, đồ thị còn có cạnh phụ.
Nhiệm vụ của bạn là tìm số cách làm cho đồ thị Dark mất tính liên thông bằng một quy trình gồm hai bước:
Đầu tiên, bạn phải cắt đúng một cạnh chính.
Sau đó, bạn phải cắt đúng một cạnh phụ.
Một cặp thao tác (cắt một cạnh chính, cắt một cạnh phụ) được coi là một cách thành công nếu sau cả hai thao tác, đồ thị bị mất tính liên thông. Lưu ý rằng, ngay cả khi việc cắt cạnh chính ở bước đầu tiên đã làm đồ thị mất liên thông, bạn vẫn bắt buộc phải cắt thêm một cạnh phụ để hoàn thành một cách hợp lệ.
Yêu cầu: Hãy đếm tổng số cắt cặp cạnh thỏa mãn yêu cầu.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và , lần lượt là số đỉnh và số cạnh phụ;
dòng tiếp theo, mỗi dòng chứa hai số nguyên và , mô tả một cạnh chính nối giữa đỉnh và ;
dòng cuối cùng, mỗi dòng chứa hai số nguyên, mô tả một cạnh phụ.
Kết quả: In ra một số nguyên duy nhất là tổng số cách hợp lệ để chia cắt đồ thị.
Ví dụ:
Dữ liệu:
4 1
1 2
2 3
1 4
3 4
Kết quả:
3
Giải thích:
Cắt cạnh với cạnh
Cắt cạnh với cạnh
Cắt cạnh với cạnh
Giới hạn: , . Dữ liệu đảm bảo đáp án không vượt quá .
Subtask #1: số điểm có ;
Subtask #2: số điểm còn lại không có ràng buộc bổ sung.
