시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

A terrible fire swept through Mouseopolis, the capital of the Great Kingdom of Mouseland. Many residents of Mouseopolis suffered great losses as the fire razed through large chunks of the town. As the residents of Mouseopolis picked themselves up and slowly put their livelihoods back together after the fire, Squeaky — the benevolent king of Mouseland — vowed to prevent such a horrifying disaster from ever occurring again.

Mouseland consists of N towns, numbered from 1 to N. There are N − 1 bidirectional roads linking towns — each road is a direct link between some pair of towns. These roads may have varying lengths. The road network is designed such that it is possible to travel between any two towns using some sequence of roads. To quickly put out any fires, Squeaky has decided that fire stations should be built in some of the towns in Mouseland. These fire stations would then be able to dispatch fire trucks to mount an effective response to fires in any town.

Squeaky’s advisors have determined that an effective response can be mounted only if the nearest fire station is no more than K kilometres away from the fire, as fire trucks would only then be able to reach the fire before the fire gets out of control. However, fire stations are expensive to maintain, so Squeaky would like to minimise the number of fire stations that need to be built.

Your task is to determine which towns fire stations should be built in, such that the required number of fire stations is minimised.

Note that fire stations may only be built in towns, and fires may only occur in towns.

입력

Your program must read from standard input.

The first line contains two integers, N and K, defined above.

N − 1 lines follow, describing the N − 1 bidirectional roads. Each of these lines contain three integers, Ai, Bi, and Di, meaning that towns Ai and Bi are linked by a bidirectional road of length Di kilometres.

출력

Your program must print to standard output.

The output should contain exactly two lines.

The first line should contain a single integer, F, the number of fire stations required.

The second line should contain exactly F distinct integers, specifying the towns in which fire stations should be built. This list may be printed in any order. If there are multiple possible ways, all of them will be accepted.

제한

  • 1 ≤ N ≤ 3 × 105
  • 1 ≤ K ≤ 1015
  • 1 ≤ Ai, Bi ≤ N for all 1 ≤ i ≤ N − 1
  • 1 ≤ Di ≤ 109 for all 1 ≤ i ≤ N − 1

예제 입력 1

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

예제 출력 1

4
1 8 3 6

Mouseland looks like this:

The minimum number of fire stations required is 4, and we can build fire stations at towns 1, 3, 6, and 8. After building fire stations at those towns, every town will be at most 4 kilometres away from the nearest fire station. Observe that the list of towns may be printed in any order.

Note that there are other valid solutions — for example, we can instead build fire stations at towns 1, 2, 5, and 8. All valid solutions will be accepted.

예제 입력 2

9 26
2 1 21
2 9 21
2 8 21
2 3 56
3 4 37
4 5 29
7 6 25
6 4 24

예제 출력 2

4
5 6 2 3

Mouseland looks like this:

The minimum number of fire stations required is 4, and we can build fire stations at towns 2, 3, 5 and 6. After building fire stations at those towns, every town will be at most 26 kilometres away from the nearest fire station. The list of towns may be printed in any order.

It happens that for this test case there are no other set of 4 towns that will satisfy the requirements.

예제 입력 3

3 18
1 2 35
2 3 49

예제 출력 3

3
1 2 3

Mouseland looks like this:

The minimum number of fire stations required is 3 — we have to build a fire station at every town.

예제 입력 4

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

예제 출력 4

2
4 10

Mouseland looks like this:

The minimum number of fire stations required is 2, and we can build fire stations at towns 4 and 10. After building fire stations at those towns, every town will be at most 3 kilometres away from the nearest fire station. The list of towns may be printed in any order.

Note that there are other valid solutions — for example, we can instead build fire stations at towns 3 and 5. All valid solutions will be accepted.