# CodeChef: June Challenge | Minimum Subtree Cover | Python, Java, C++ Solution

You are given a tree with nn vertices (numbered 1,2,…,n1,2,…,n) and an integer kk.

A subtree is defined as a connected subgraph of the tree. That is, a subtree is another tree that can be obtained by removing some (possibly none) vertices and all edges incident to those vertices from TT.

A subset SS of vertices is called good if every subtree containing all the nodes in SS has at least kk nodes.

Find the **size of the smallest good subset**.

Input

- The first line contains a single integer TT, the number of test cases. The descriptions of test cases follow.

- The first line of each testcase contains two integers, nn and kk.

- The next n−1n−1 lines each contains two integers uu, vv, denoting an edge between vertices uu and vv of the tree.

Output

- For each test case print in a single line, the minimum size of a good subset.

Constraints

- 1≤n≤1051≤n≤105

- 1≤k≤n1≤k≤n

- 1≤u,v≤n1≤u,v≤n

- The given edges for each test case form a tree.

- The sum of nn over all test cases is at most 106106.

Subtasks

**Subtask #1 (30 points):** 1≤n≤1031≤n≤103

**Subtask #2 (70 points):** original constraints

Sample Input

2

7 5

1 2

2 3

3 4

3 5

5 6

3 7

6 4

1 2

1 3

1 4

1 5

1 6

Sample Output

2

3

Explanation

**Test Case 11:** Consider the set S={1,6}S={1,6}.

The smallest subtree that contains both of the vertices in SS is the path between them (1→2→3→5→61→2→3→5→6) which contains 55 vertices. Hence for k=5k=5, the answer is 22.

**Test Case 22:** Consider the set S={2,3,4}S={2,3,4}.

The smallest subtree that contains these three vertices includes 44 nodes {1,2,3,4}{1,2,3,4}.

**Solution**

Due to copyright issues we won’t be able to update the solution here immediately. However you can **download the code file from our telegram channel**. So join our telegram channel for further updates. Keep tracking, the solution will be updated on this website soon.

*Read more post** Here*