Stuck on graph algorithm task

Question

I'm currently trying to solve an algorithm problem from last year's Polish Collegiate Championships which reads as follows:

The Lord Mayor of Bytetown plans to locate a number of radar speed cameras in the city. There are n intersections in Bytetown numbered from 1 to n, and n-1 two way street segments. Each of these street segments stretches between two intersections. The street network allows getting from each intersection to any other.

The speed cameras are to be located at the intersections (maximum one per intersection), wherein The Lord Mayor wants to maximise the number of speed cameras. However, in order not to aggravate Byteland motorists too much, he decided that on every route running across Bytetown roads that does not pass through any intersection twice there can be maximum k speed cameras (including those on endpoints of the route). Your task is to write a program which will determine where the speed cameras should be located.

Input

The first line of input contains two integers n and k (1 <= n, k <= 1000000): the number of intersections in Bytetown and maximum number of speed cameras which can be set up on an individual route. The lines that follow describe Bytetown street network: the i-th line contains two integers a_i and b_i (1 <= a_i, b_i <= n), meaning that there is a two-way street segment which joins two intersections numbered a_i and b_i.

Output

The first output line should produce m: the number describing the maximum number of speed cameras, that can be set up in Byteland. The second line should produce a sequence of m numbers describing the intersections where the speed cameras should be constructed. Should there be many solutions, your program may output any one of them. Example

For the following input data:

5 2
1 3
2 3
3 4
4 5

one of the correct results is:

3
1 2 4

So judging by how many teams solved it, I'm guessing it can't be too hard but still, I got stuck almost immediately with no idea as to how to move on. Since we know that "on every route running across Bytetown roads that does not pass through any intersection twice there can be maximum k speed camera", I guess we first have to somehow dissect the graphs into components being possible routes around the town. This alone seems like a really hard thing to do cause supposing there's an intersection with four motorways coming out of it, it already creates three possible directions for every enter point, thus making 12 routes. Not to mention how the situation complicates when there's more such four-handed intersections.

Maybe I'm approaching the task from the wrong angle? Could you please help?

Answer 1

It seems greedy works here

while k >= 2  
    mark all leaves of the tree and remove them
    k = k - 2;

if ( k == 1 ) 
   mark any 1 of remaining vertices