|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||29||21||4||44.444%|
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 Ai-th city and the Bi-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.
Write K lines on your submission file. The j-th line of the output contains two integers Xj, Yj (1 ≦ Xj ≦ N, 1 ≦ Yj ≦ N), representing the cities connected by a road to construct.
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/W0
Here, the score you gain for the input is min(P, P × 20S) The score for this task is the sum of the scores for each input.
The values of N, K, W0, P on each input are as follows:
4 1 8 1 2 2 3 3 4
In addition to the existing roads, by constructing a road connecting the 1-st city and the 4-th city, the total distance becomes 8.
Let P = 10 for this input. Here, S = 0, thus the score is 10 points.
4 1 8 1 2 2 3 3 4
In this case, the total distance is 10 after constrcting the road.
Let P = 10 for this input. Here, S = −0.25, thus the score is 4.728 · · · points.