401736: GYM100519 H Holes

In this problem, we investigate the life of rabbits.

Our rabbits live in the glades, some of which are connected with two-way trails. No trail makes a loop: each of them connects two different glades. There is at most one trail between any pair of glades.

Our rabbits can dig holes in the ground where they can hide in case of danger. The holes can be dug in the center of each glade. In order for the rabbit to hide in the hole, the rabbit just needs to get to the glade where the hole is located, and then it hides there immediately. Each hole can accommodate any number of rabbits.

The rabbit universe has two important features: there is a path between any two glades, and each glades except at most one is connected with no more than two other glades.

Rabbits want to make some holes so that in case of danger, they can minimize the time for all rabbits to hide. Help them find the right glades to dig the holes. The time is calculated as a number of trails a rabbit uses to get to the hole. All rabbits are traveling and hiding independently.

It is also assumed that there are so many rabbits that each glade has at least one of them.

The first line of input contains integers N, M and K: the number of glades, the number of trails and the number of holes to be dug respectively (1 ≤ K ≤ N ≤ 1000).

Each of the next M lines describes one trail and contains two integers x_i and y_i: the numbers of glades that are connected by this trail (1 ≤ x_i, y_i ≤ N).

Output a single integer: the minimum possible amount of time needed for all rabbits to hide in case all K holes are placed optimally.

5 6 1
3 1
3 2
3 4
3 5
1 2
4 5

1

8 8 2
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8

2