21800번 - Road Service 6 점수다국어

There are N cities in IOI kingdom, numbered from 1 to N. There are also N − 1 bidirectional roads, numbered from 1 to N − 1. The i-th road connects the A_i-th city and the B_i-th city. There exists a path between any pair of vertices.

The distance between two cities are defined as the smallest number of roads which connect the two cities. The total distance of IOI kingdom is defined as the sum of the distances between all pair of different cities.

The king of IOI kingdom plans to construct K additional roads in order to reduce the total distance and improve convenience.

You, as an assistant of the king, help the king by finding a good plan.

Given the information of existing roads in IOI kingdom and the number of roads to construct, output a plan for constructing K roads. The less the total distance is, the more points you gain.

There are 6 inputs for this task. Read the following data from each input.

• The first line of input contains three space separated integers N, K and W₀. These mean that IOI kingdom has N cities and that the king plans to construct K roads. W₀ is a parameter for scoring.
• The i-th (1 ≦ i ≦ N − 1) line of the following N − 1 lines contains integers A_i and B_i, the cities which the i-th road connects.

Write K lines on your submission file. The j-th line of the output contains two integers X_j, Y_j (1 ≦ X_j ≦ N, 1 ≦ Y_j ≦ N), representing the cities connected by a road to construct.

• 1 ≦ N ≦ 1 000.
• 1 ≦ A_i < B_i ≦ N (1 ≦ i ≦ N − 1).
• (A_i , B_i) ≠ (A_k, B_k) (1 ≦ i < k ≦ N − 1).
• There are a path between any pair of cities.

For each inputs, your score is calculated as follows:

If your output does not follow the format, your score is zero point. Otherwise, let the total distance after constructing the roads according to your plan be W, and let the point for the input be P. Let us define

S = 1.0 − W/W₀

Here, the score you gain for the input is min(P, P × 20^S) The score for this task is the sum of the scores for each input, rounded to the nearest integer.

The values of N, K, W₀, P on each input are as follows: