8810: [CSES Problem Set] Creating Offices
[Creator : ]
Description
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?
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?
Input
The first input line has two integers n and d: the number of cities and the minimum distance. The cities are numbered 1,2,…,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.
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.
Output
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.
Constraints
$1≤n,d≤2⋅10^5$
$1≤a,b≤n$
$1≤a,b≤n$
Sample 1 Input
5 3
1 2
2 3
3 4
3 5
Sample 1 Output
2
1 4