Một Trung tâm nghiên cứu tuyệt mật (mà chúng ta không có quyền nói rõ tên ở đây) có phòng thí nghiệm đặt ngầm trong lòng đất. Các phòng thí nghiệm được đánh số từ đến . Giữa một số phòng có đường hầm nối với nhau, sao cho từ một phòng bất kỳ có thể đi đến phòng bất kỳ khác (có thể phải đi qua một số phòng nào đó). Độ dài mỗi đường hầm là như nhau và thời gian đi hết một đường hầm là . Không có đường hầm nào nối một phòng với chính nó, nhưng có thể có nhiều đường hầm cùng nối phòng với nhau và tổng cộng trong Trung tâm có tất cả đường hầm . Đường hầm cho phép đi lại theo cả hai chiều. Có phòng có lối thoát hiểm lên mặt đất . Trong trường hợp sơ tán khẩn cấp, tất cả các nhân viên phải tập trung ở những phòng có lối thoát hiểm.
Yêu cầu: Hãy xác định thời gian tối thiểu để nhân viên mỗi phòng tập trung về phòng có lối thoát hiểm trong trường hợp phải sơ tán khẩn cấp.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên và ;
Dòng thứ hai chứa số nguyên khác nhau cho biết các phòng có cửa thoát hiểm;
Dòng thứ ba chứa số nguyên ;
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên xác định cặp phòng có đường hầm nối trực tiếp.
Dữ liệu ra:
Một dòng chứa số nguyên, số thứ xác định thời gian tối thiểu để nhân viên phòng đi được tới phòng có lối thoát hiểm.
