CSES - Creating Offices
  • Time limit: 1.00 s
  • Memory limit: 512 MB

There are n cities and n-1 roads between them. There is a unique route between any two cities, and their distance is the number of roads on that route.

A company wants to have offices in some cities, but the distance between any two offices has to be at least d. What is the maximum number of offices they can have?


The first input line has two integers n and d: the number of cities and the minimum distance. The cities are numbered 1,2,\dots,n.

After this, there are n-1 lines describing the roads. Each line has two integers a and b: there is a road between cities a and b.


First print an integer k: the maximum number of offices. After that, print the cities which will have offices. You can print any valid solution.


  • 1 \le n,d \le 2 \cdot 10^5
  • 1 \le a,b \le n



5 3
1 2
2 3
3 4
3 5


1 4