B"Sonya likes ice cream very much. She eats it even during programming competitions. That is why the girl decided that she wants to open her own ice cream shops. Sonya lives in a city with n junctions and n-1 streets between them. All streets are two-way and connect two junctions. It is possible to travel from any junction to any other using one or more streets. City Hall allows opening shops only on junctions. The girl cannot open shops in the middle of streets. Sonya has exactly k friends whom she can trust. If she opens a shop, one of her friends has to work there and not to allow anybody to eat an ice cream not paying for it. Since Sonya does not want to skip an important competition, she will not work in shops personally. Sonya wants all her ice cream shops to form a simple path of the length r ( 1 <= r <= k ), i.e. to be located in different junctions f_1, f_2, ... , f_r and there is street between f_i and f_{i+1} for each i from 1 to r-1 . The girl takes care of potential buyers, so she also wants to minimize the maximum distance between the junctions to the nearest ice cream shop. The distance between two junctions a and b is equal to the sum of all the street lengths that you need to pass to get from the junction a to the junction b . So Sonya wants to minimize max_{a} min_{1 <= i <= r} d_{a,f_i} where a takes a value of all possible n junctions, f_i -- the junction where the i -th Sonya's shop is located, and d_{x,y} -- the distance between the junctions x and y . Sonya is not sure that she can find the optimal shops locations, that is why she is asking you to help her to open not more than k shops that will form a simple path and the maximum distance between any junction and the nearest shop would be minimal. The first line contains two integers n and k ( 1 <= q k <= q n <= q 10^5$$"...