Đây là bài chỉ nộp kết quả (output-only). Với mỗi dữ liệu vào được cung cấp, bạn cần nộp tệp kết quả, không phải chương trình sinh kết quả.

Vương quốc IOI có \(N\) thành phố được đánh số từ \(1\) đến \(N\) và \(N-1\) con đường hai chiều được đánh số từ \(1\) đến \(N-1\). Con đường thứ \(i\) nối hai thành phố \(A_i\) và \(B_i\). Có đường đi giữa mọi cặp thành phố.

Khoảng cách giữa hai thành phố là số con đường ít nhất cần đi qua để đi từ thành phố này đến thành phố kia. Tổng khoảng cách của vương quốc là tổng khoảng cách trên tất cả các cặp thành phố khác nhau, mỗi cặp không có thứ tự được tính một lần.

Nhà vua dự định xây thêm \(K\) con đường để giảm tổng khoảng cách, giúp việc đi lại thuận tiện hơn. Là phụ tá của nhà vua, bạn hãy tìm một phương án xây đúng \(K\) con đường. Tổng khoảng cách sau khi xây càng nhỏ thì điểm số càng cao.

Dữ liệu vào

Bài có sáu dữ liệu vào. Mỗi dữ liệu có dạng:

• Dòng đầu chứa ba số nguyên \(N,K,W_0\). Trong đó \(N\) là số thành phố, \(K\) là số con đường cần xây thêm, còn \(W_0\) là tham số dùng để tính điểm.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), mô tả con đường có sẵn thứ \(i\).

Dữ liệu ra

Với mỗi dữ liệu vào, nộp một tệp kết quả gồm đúng \(K\) dòng. Dòng thứ \(j\) chứa hai số nguyên \(X_j,Y_j\), với \(1 \le X_j,Y_j \le N\), biểu thị hai thành phố được nối bởi con đường xây thêm thứ \(j\).

Kết quả chỉ hợp lệ nếu tuân theo định dạng trên. Có thể xây thêm đường nối một cặp thành phố vốn đã có đường nối, như trong ví dụ 2.

Ràng buộc

• \(1 \le N \le 1\,000\).
• \(1 \le A_i < B_i \le N\) với \(1 \le i \le N-1\).
• \((A_i,B_i) \ne (A_k,B_k)\) với \(1 \le i < k \le N-1\).
• Có đường đi giữa mọi cặp thành phố.

Chấm điểm

Với mỗi dữ liệu vào, kết quả sai định dạng nhận \(0\) điểm. Nếu kết quả hợp lệ, gọi \(W\) là tổng khoảng cách sau khi xây thêm các con đường theo phương án của bạn, và \(P\) là số điểm tối đa của dữ liệu đó. Đặt

Điểm cho dữ liệu này là

Điểm của bài là tổng điểm của sáu dữ liệu, sau đó làm tròn đến số nguyên gần nhất.

Các tham số của sáu dữ liệu vào như sau:

Ví dụ

4 1 8
1 2
2 3
3 4

1 4

4 1 8
1 2
2 3
3 4

1 2

Nguồn

JOI 2018 Spring Training Camp, ngày 2 - Road Service.