# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Pretty Diabolical!

By ridzz007 · Limits 1s, 512 MB

TRAOMBINNAA is going to be Billy Butcher's base for the next season of the boys. He is going to build a forest around it to fool Homlander in case of any attack. As Homlander has weakness staring at similar looking objects, Butcher will build the forest with several K-beautiful trees.

Now, you’re given a tree consisting of n nodes. Find the number of nodes needed to make the tree K-beautiful, or state that it’s impossible so that Butcher can put away that tree. You can select any node as the root node in this problem. Recall that a tree is a connected acyclic undirected graph with n nodes and n-1 edges.
A K-beautiful tree is such that at least one of its child node has distance K from the root and all other child with distance from root less than or equal to K. Note that a tree can have several beautiful configurations considering different root node. For clear understanding, look at the given pictures below.

## Input

Input starts with T, the number of test cases. The first line of each test case consists of two integers, N and K, the number of nodes in the tree and the required beautiful configuration. Each of the next N-1 lines consists of two integers a and b, denoting an edge between node a and node b.

1 ≤ T ≤ $10^{5}$

1 ≤ N ≤ $10^{5}$

1 ≤ K ≤ $10^{18}$

1 ≤ a, b ≤ N

Sum of N over all test cases does not exceed $10^{5}$.

## Output

for each test case, print the minimum number of nodes needed to be added to the tree for making it a K-beautiful tree. If it’s impossible to build a K-beautiful tree, print -1.

## Sample

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

-1
3


### Statistics

50% Solution Ratio

YouKnowWhoEarliest, 6M ago

prodip_bsmrstuFastest, 0.0s

prodip_bsmrstuLightest, 11 MB

YouKnowWhoShortest, 1111B