시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 16 14 14 87.500%

문제

You are given a tree T and an integer K. You can choose arbitrary distinct two vertices u and v on T. Let P be the simple path between u and v. Then, remove vertices in P, and edges such that one or both of its end vertices is in P from T. Your task is to choose u and v to maximize the number of connected components with K or more vertices of T after that operation.

입력

The input consists of a single test case formatted as follows.

N K
u1 v1
.
.
.
uN-1 vN-1

The first line consists of two integers N, K (2 ≤ N ≤ 100,000, 1 ≤ KN). The following N-1 lines represent the information of edges. The (i+1)-th line consists of two integers ui, vi (1 ≤ ui, viN and uivi for each i). Each {ui, vi} is an edge of T. It's guaranteed that these edges form a tree.

출력

Print the maximum number of connected components with K or more vertices in one line.

예제 입력 1

2 1
1 2

예제 출력 1

0

예제 입력 2

7 3
1 2
2 3
3 4
4 5
5 6
6 7

예제 출력 2

1

예제 입력 3

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

예제 출력 3

4

예제 입력 4

3 1
1 2
2 3

예제 출력 4

1

예제 입력 5

3 2
1 2
2 3

예제 출력 5

0

예제 입력 6

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

예제 출력 6

2