Nhằm chuẩn bị cho hội nghị thượng đỉnh Mỹ - Triều lần thứ tư thành công tốt đẹp, mang lại hiệu quả thực chất, mang lại hòa bình, thịnh vượng trên bán đảo Triều Tiên và khu vực. Việt Nam đã nhận đăng cai sự kiện này. Việt Nam có khách sạn hạng sang, có con đường hai chiều nối giữa khách sạn này, nhằm tạo cho hai bên tham gia đàm phán vui vẻ nhất thì nước chủ nhà phải bố trí sao cho khoảng cách từ chỗ ăn nghỉ đến nơi đàm phán của hai bên có độ dài như nhau (độ dài tính bằng số cạnh). Do Mỹ và Triều Tiên còn chưa tin tưởng lẫn nhau nên đã bí mật gửi các phương án chỗ ăn nghỉ mà mình chọn cho Việt Nam. Nước chủ nhà cần phải tính toán sẵn phương án bố trí nơi đàm phán thỏa mãn từng yêu cầu trên của Mỹ và Triều Tiên. Mỗi khách sạn hạng sang đều đáp ứng được tất cả các nhu cầu về ăn nghỉ và cũng có thể là nơi đàm phán.
Coi bản đồ thể hiện vị trí của khách sạn là cây gốc tại đỉnh .
Dữ liệu vào:
Dòng đầu tiên là hai số ;
Dòng tiếp theo chứa số có nghĩa là có cạnh nối trực tiếp đến ;
dòng tiếp theo thể hiện thông tin về khách sạn mà Mỹ, Triều Tiên lựa chọn làm nơi ăn nghỉ, dòng thứ có hai số .
Dữ liệu ra:
Gồm dòng, mỗi dòng là số khách sạn có thể chọn để đảm bảo yêu cầu.
