judete

In Monkey Land there are N cities numbered from 1 to N. The cities are connected by roads, in such a manner that there is a unique path between any 2 cities in the country. Not being able to manage all the cities the President decides the following:

  1. the country will be divided into counties, so that every city will belong to a single county
  2. the path between any 2 cities located in the same county will not pass through cities from other counties
  3. the minimum number of cities in a county is K
Be there T the maximum number of cities belonging to the same county.

Task

Write a program that finds a county distribution solution for a given configuration of cities and roads, with T being the minimum.

Input Data

The first line of input file judete.in contains the two positive integers, N and K, separated by a single space.
The following N-1 lines contain two positive integers between 1 and N, separated by a space, representing two cities connected by a road.

Output Data

The first line of file judete.out will contain T minimum for the input file configuration.

Constraints

Example

judete.in

judete.out

Explanation 

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

4

A possible division of cities in counties is:
1, 2, 10
3, 4, 5
6, 7, 8, 9
Each city belongs to only one county.
Each county contains at least 3 cities.
The maximum number of cities in a county is 4 (and this is also the minimum possible).

Time limit: 0.1 seconds/test

Fechete Dan Ionut
University of Bucharest
Mathematics and Informatics Department
mailto:f_dany@eminem.com