Cho một đồ thị vô hướng có trọng số đơn giản. Bạn không chỉ hài lòng với việc tìm ra một cây khung nhỏ nhất (MST) của đồ thị này, mà còn muốn biết có bao nhiêu cây khung nhỏ nhất khác nhau trong đồ thị. (Hai cây khung nhỏ nhất được coi là khác nhau nếu có ít nhất một cạnh khác nhau giữa chúng).
Dữ liệu:
Dòng đầu tiên chứa hai số và , biểu thị số lượng nút và số lượng cạnh của đồ thị vô hướng. Các nút được đánh số nguyên từ .
dòng tiếp theo, mỗi dòng chứa ba số nguyên: , biểu thị cạnh nối giữa nút và nút có trọng số là .
Kết quả:
Xuất ra số lượng cây khung nhỏ nhất khác nhau. Bạn chỉ cần xuất kết quả sau khi lấy phần dư cho .
Ví dụ:
Dữ liệu:
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Kết quả:
8
Giới hạn:
Đối với tất cả dữ liệu: .
Dữ liệu đảm bảo không có cạnh nối chính nó (khuyên) và cạnh lặp (đa cạnh).
Lưu ý: Số lượng các cạnh có cùng trọng số sẽ không vượt quá .
