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 ≤ 105 10^{5}

1 ≤ N ≤ 105 10^{5}

1 ≤ K ≤ 1018 10^{18}

1 ≤ a, b ≤ N

Sum of N over all test cases does not exceed 105 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

    Discussion

    Statistics


    50% Solution Ratio

    YouKnowWhoEarliest, 6M ago

    prodip_bsmrstuFastest, 0.0s

    prodip_bsmrstuLightest, 11 MB

    YouKnowWhoShortest, 1111B

    Submit

    Login to submit