시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB367621.429%

문제

You are given a tree on $n$ vertices. Suppose we are at the vertex $v$. In one step we can go from $v$ to any other vertex $u$ such that there are exactly $d$ edges on the shortest path between $v$ and $u$. A vertex $u$ is reachable from $v$ if we can get to $u$ from $v$ using zero or more steps.

Naturally, all vertices can be divided into reachability classes. A reachability class is a set of vertices $C$ such that any vertex in $C$ is reachable from any other vertex in $C$, but no vertex which is not in $C$ is reachable from any vertex in $C$. How many reachability classes are there in the given tree?

입력

The first line contains two space-separated integers $n$ and $d$ ($1 \leq n \leq 10^6$, $0 \leq d \leq n$).

Next $n - 1$ lines describe edges of the tree. Each line contains two space-separated integers --- indices of vertices connected by the corresponding edge. Indices are 1-based.

출력

Print one integer --- the number of reachability classes.

예제 입력 1

4 2
1 2
2 3
3 4

예제 출력 1

2