THỰC HÀNH

Hệ thống đường cao tốc hiện tại ở thành phố A mới đảm bảo đi lại giữa một số nút giao thông trọng điểm và còn nhiều nút giao thông trọng điểm chưa có đường cao tốc qua nó. Để giải toả tình trạng ách tắc giao thông trong thành phố, chính quyền thành phố quyết định phát triển hệ thống đường cao tốc của thành phố sao cho có thể đi lại giữa hai nút giao thông trọng điểm bất kỳ. Có N nút giao thông trọng điểm, được đánh số từ 1 đến N. Nút giao thông i được cho bởi toạ độ (x_i, y_i) trong hệ toạ độ Đề các. Mỗi tuyến đường cao tốc nối hai nút giao thông trọng điểm. Tất cả các tuyến đường hiện có cũng như sẽ được phát triển được xây dựng theo đường thẳng nối chúng, vì thế độ dài của mỗi tuyến đường chính là khoảng cách giữa hai điểm tương ứng với hai nút giao thông trọng điểm. Tất cả các tuyến đường cao tốc là hai chiều. Các tuyến đường có thể cắt nhau nhưng người sử dụng phương tiện giao thông chỉ được đổi tuyến đi ở các nút giao thông là đầu mút của các tuyến đường (do hệ thống cao tốc nên những chỗ cắt nhau được thiết kế cầu vượt, không thể rẽ tại những chỗ này).

Chính quyền thành phố muốn tìm cách xây dựng bổ sung một số tuyến đường cao tốc nối các nút giao thông trọng điểm với chi phí nhỏ nhất đảm bảo sự đi lại giữa mọi nút giao thông trọng điểm. Chi phí xây dựng tỷ lệ thuận với độ dài của tuyến đường, vì vậy bạn có thể tính chi phí xây dựng các tuyến đường bổ sung như là tổng độ dài của các tuyến đường cần xây dựng.

Dữ liệu vào:

• Dòng đầu tiên chứa số N (1 ≤ N ≤ 750)
• Dòng thứ i trong số N dòng tiếp theo chứa toạ độ (x_i, y_i) của nút giao thông trọng điểm i (|x_i|, |y_i| ≤ 10⁵).
• Dòng tiếp theo chứa M là số tuyến đường cao tốc hiện có (0 ≤ M ≤ 1000)
• Dòng thứ j trong số M dòng tiếp theo chứa hai chỉ số của hai nút giao thông là đầu mút của tuyến đường j

Dữ liệu ra:

• Dòng đầu tiên chứa số K là số lượng tuyến đường cần  xây dựng  bổ sung
• Dòng thứ i trong số K dòng tiếp theo chứa hai chỉ số của hai nút giao thông là đầu mút của tuyến đường cần xây dựng bổ sung thứ i

Ví dụ:

Dữ liệu vào:
9
1 5
0 0
3 2
4 5
5 1
0 4
5 2
1 2
5 3
4 
1 3
9 7
1 2
2 3

Dữ liệu ra:
5
1 6
3 7
4 9
5 7
8 3