Tree Cutting

Interview

Time limit2sMemory limit128 MB

Summary

Given a tree with n vertices, find the minimum number of edges to cut so some resulting piece has exactly m vertices, or report impossibility.

Level: Medium5 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

A tree is a connected graph with no cycles. Cutting one edge of a tree splits it into two trees.

You are given a tree with n vertices. Cut some edges so that at least one remaining connected component is a tree with exactly m vertices. Find the minimum number of edges that must be cut.

Input

The first line contains n (1 ≤ n ≤ 150) and m (1 ≤ m ≤ n). Each of the next n-1 lines contains two integers A and B describing an edge of the tree. This means that vertex A and vertex B are connected.

Output

Print the minimum number of edges that must be cut to obtain a tree with exactly m vertices. If it cannot be done, print -1.

Examples1

Example 1
Input
```
8 5
1 2
6 1
7 6
8 6
1 3
5 3
4 3
```
Expected output
```
1
```