시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB101010100.000%

## 문제

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.

• The first line of input contains three space separated integers N, K and W0. These mean that IOI kingdom has N cities and that the king plans to construct K roads. W0 is a parameter for scoring.
• The i-th (1 ≦ i ≦ N − 1) line of the following N − 1 lines contains integers Ai and Bi, 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 Xj, Yj (1 ≦ Xj ≦ N, 1 ≦ Yj ≦ N), representing the cities connected by a road to construct.

## 제한

• 1 ≦ N ≦ 1 000.
• 1 ≦ Ai < Bi ≦ N (1 ≦ i ≦ N − 1).
• (Ai , Bi) ≠ (Ak, Bk) (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/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, rounded to the nearest integer.

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

Input Data N K W0 P
1 20 4 512 10
2 1000 100 2650000 18
3 1000 300 1755000 18
4 1000 100 2900000 18
5 1000 100 2690000 18
6 1000 300 1745000 18

## 예제 입력 1

4 1 8
1 2
2 3
3 4


## 예제 출력 1

1 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.

## 예제 입력 2

4 1 8
1 2
2 3
3 4


## 예제 출력 2

1 2


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.

## 채점 및 기타 정보

• 18점 이상을 획득해야 를 받는다.
• 예제는 채점하지 않는다.