{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\nChính phủ Bangladesh đang nghiêm túc xem xét giảm bớt tình trạng kẹt xe không thể chịu đựng được ở Dhaka. Họ đã thử nhiều cách để giải quyết vấn đề này. Nhưng tất cả bạn biết khi di chuyển ở Dhaka, gần như là không thể tránh khỏi điều đó :-). Cơ quan cao cấp của Chính phủ hiện đã nhận ra tình hình rằng họ cần một cái nhìn và hành động khác biệt cho nhiệm vụ khổng lồ này. Họ đã đến với bạn và với tư cách là một chuyên gia về khoa học máy tính, bạn đã đưa ra cho họ một giải pháp. Ý tưởng là đơn giản, đó là xây dựng các con đường mới. Nhưng vấn đề là đảm bảo rằng con đường mới được xây dựng được sử dụng một cách hợp lý. Và điều đó chỉ xảy ra nếu chi phí di chuyển được giảm cho một số tuyến đường. Trong trường hợp đó, giao thông trên những tuyến đường đó sẽ tự động sử dụng con đường hiện tại và do đó sẽ được phân bổ tốt hơn trong mạng lưới.\n\nTrong bài toán này, bạn sẽ được cung cấp một bản đồ của Dhaka dưới dạng một đồ thị không hướng. Mỗi nút sẽ biểu thị một trạm và cạnh sẽ biểu thị một con đường. Các nút sẽ là các điểm hình học 2-D đơn giản và chi phí để di chuyển một con đường tỷ lệ với khoảng cách Euclidian giữa hai nút. Bây giờ, bạn sẽ đề xuất xây dựng một con đường tạm thời. Bạn đã cố định tiêu chí để chọn hai nút giữa đó con đường mới sẽ được xây dựng.\n\nNếu có một con đường giữa (u, v) thì cặp này sẽ không được xem xét.\nNgược lại, $C_{uv} \u003d Sum(PreCost_{ij} — CurCost_{ij})$ với $CurCost_{ij}$ là chi phí đường đi ngắn nhất từ $i$ đến $j$ nếu con đường giữa (u, v) tồn tại. Và $PreCost_{ij}$ là chi phí đường đi ngắn nhất trước khi xây dựng con đường giữa u và v.\nCặp (u,v) với $C_{uv}$ lớn nhất sẽ được chọn.\n\n### Đầu vào\nMỗi trường hợp kiểm tra bắt đầu với hai số nguyên dương N (\u003c 50) và M (\u003c 1225). Trong vài dòng tiếp theo, tọa độ (x, y) của các nút sẽ được cung cấp. Giá trị của mỗi tọa độ sẽ nằm trong phạm vi từ -1000 đến 1000. Trong vài dòng tiếp theo, mô tả con đường sẽ được cung cấp. Mỗi con đường bao gồm hai số nguyên dương (u, v) nơi 1 \u003c u,v \u003c N. Điều này có nghĩa là có một con đường hai chiều giữa u và v. Đồ thị được đảm bảo là liên thông.\nĐầu vào kết thúc bởi N \u003d M \u003d 0. Trường hợp này không được xử lý.\n\n### Đầu ra\nNếu việc xây dựng đường mới giúp cải thiện tình hình giao thông thì đầu ra sẽ là cặp nút (u, v) giữa đó con đường mới sẽ được xây dựng. Nếu có nhiều ứng cử viên thì các nút có khoảng cách ngắn nhất sẽ được chọn. Nếu lại có sự đồng hòa thì cặp nút có chỉ số nhỏ sẽ là câu trả lời.\nMặt khác, nếu mạng lưới đường bộ đã cân bằng (Đường mới sẽ không cải thiện tình hình giao thông), in ra `No road required`. Lưu ý rằng, nếu Cuv nhỏ hơn hoặc bằng 1.0 thì mạng lưới sẽ được coi là cân bằng.\n\n### Ví dụ \n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 6\n0 0 0 2 2 0 2 2\n1 2 1 3 1 4\n2 3 2 4\n3 4\n4 4\n0 0 0 2 2 0 2 2\n1 2 2 3 3 4 4 1\n4 3\n0 0 0 2 2 0 2 2\n1 2 2 3 3 4\n0 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNo road required\n1 3\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}