Cho một đồ thị vô hướng liên thông dạng cây gồm đỉnh và cạnh. Các đỉnh được đánh số từ đến . Độ dài của mỗi cạnh là 1 đơn vị. Ban đầu, giữa hai đỉnh bất kỳ luôn tồn tại một đường đi duy nhất.
Trên cây này, có đỉnh được đánh dấu là các "đỉnh nguồn". Một đỉnh có thể được đánh dấu nhiều lần (đa tập hợp nguồn).
Yêu cầu bài toán là loại bỏ một số lượng cạnh tối đa khỏi cây ban đầu, sao cho đồ thị kết quả (lúc này là một rừng gồm các cây con) thỏa mãn điều kiện: Từ bất kỳ đỉnh nào trong đồ thị, khoảng cách ngắn nhất đến một đỉnh nguồn thuộc cùng thành phần liên thông không vượt quá .
Hãy xác định số lượng cạnh tối đa có thể loại bỏ và chỉ số của các cạnh đó.
Dữ liệu:
Dòng đầu tiên chứa ba số nguyên và () — lần lượt là số lượng đỉnh của cây, số lượng đỉnh nguồn và giới hạn khoảng cách cho phép.
Dòng thứ hai chứa số nguyên () — chỉ số của các đỉnh nguồn được đánh dấu.
dòng tiếp theo, dòng thứ chứa hai số nguyên và () — hai đỉnh được nối bởi cạnh có chỉ số .
Đảm bảo rằng đồ thị ban đầu là liên thông (một cây) và khoảng cách từ bất kỳ đỉnh nào đến đỉnh nguồn gần nhất không vượt quá .
Kết quả:
Dòng đầu tiên in ra một số nguyên cho biết số lượng cạnh tối đa có thể loại bỏ.
Dòng thứ hai in ra số nguyên phân biệt là chỉ số của những cạnh bị loại bỏ (theo thứ tự đầu vào, 1-based). Nếu có nhiều phương án, in ra một phương án bất kỳ.
Ví dụ:
Dữ liệu:
6 2 4
1 6
1 2
2 3
3 4
4 5
5 6
Kết quả:
1
5
Dữ liệu:
6 3 2
1 5 6
1 2
1 3
1 4
1 5
5 6
Kết quả:
2
4 5
Giới hạn:
Subtask #1 (10% số điểm): .
Subtask #2 (20% số điểm): .
Subtask #3 (15% số điểm): .
Subtask #4 (15% số điểm): .
Subtask #5 (40% số điểm): . Không có ràng buộc gì thêm.
