- Prepare
- Algorithms
- Dynamic Programming
- Far Vertices

# Far Vertices

# Far Vertices

You are given a tree that has N vertices and N-1 edges. Your task is to mark as small number of vertices as possible, such that, the maximum distance between two unmarked vertices is less than or equal to K. Output this value. Distance between two vertices i and j is defined as the minimum number of edges you have to pass in order to reach vertex i from vertex j.

**Input Format**

The first line of input contains two integers N and K. The next N-1 lines contain two integers (ui,vi) each, where 1 <= ui,vi <= N. Each of these lines specifies an edge.

N is no more than 100. K is less than N.

**Output Format**

Print an integer that denotes the result of the test.

**Sample Input:**

```
5 1
1 2
1 3
1 4
1 5
```

**Sample Output:**

```
3
```

**Sample Input:**

```
5 2
1 2
1 3
1 4
1 5
```

**Sample Output:**

```
0
```

**Explanation:**

In the first case you have to mark at least 3 vertices, and in the second case you don't need to mark any vertices.