C. Shareefeh's Bar Fi Ard-El-Dyar
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the previous season, Shareefeh convinced Abu Shehab to plant a tree in Ard El Dyar. Over time, the tree grew larger and now consists of $$$n$$$ nodes.

Interestingly, Shareefeh's tree has leaves — and while everyone in Haret El Dabe3 knows what a leaf is, we'll redefine it here just in case Abo Bader forgets again: a leaf is a node that has no children.

One day, Em Zeki came over to chat with Shareefeh about life. During the conversation, Shareefeh asked her to talk about Em Sam3o Mart El7ares, and why she's currently the talk of the town in Haret El Dabe3 — clearly showing that Shareefeh was feeling jealous. It's worth noting that Abo Khater had a crush on Em Sam3o Mart El 7ares.

Em Zeki told Shareefeh that Em Sam3o, Mart El 7ares, had recently solved an impressive problem that caught everyone's attention. Feeling a bit competitive, Shareefeh decided she wanted to do something similar — but using her own tree. The challenge was this: Shareefeh needed to find out how many leaves she could choose from her tree such that the set $$$S$$$ that contains of the Lowest Common Ancestor (LCA) of every pair of selected leaves has $$$x$$$ unique nodes. Note that Shareefeh might not be able to accomplish this and reach the level of Em Sam3o Mart El 7ares — in that case, print -1.

Note that Shareefeh's tree is rooted at node $$$1$$$.

The Lowest Common Ancestor (LCA) is defined between two nodes v and w as the lowest node in the tree that has both v and w as descendants.

For example in following tree which is rooted at node $$$1$$$:

LCA between nodes $$$4$$$ and $$$6$$$ is $$$2$$$.

LCA between nodes $$$8$$$ and $$$3$$$ is $$$7$$$.

LCA between nodes $$$5$$$ and $$$7$$$ is $$$7$$$.

LCA between nodes $$$4$$$ and $$$8$$$ is $$$1$$$.

Input

The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.

For each test case

The first line of input contain two integers $$$n$$$ and $$$x$$$ $$$(2 \leq n, x \leq 2 \cdot 10^5)$$$ — denotes the number of nodes the tree has and the number of unique LCAs required.

The next $$$n − 1$$$ lines of each test case contain two integers each — $$$u$$$, $$$v$$$ indicating an edge between $$$u$$$ and $$$v$$$ $$$(1 \le u,v \le n)$$$ representing a tree.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case print the minimum number of leaves needed to achieve $$$x$$$ unique lowest common ancestors (LCAs). Or print -1 in case there is no answer

Example
Input
3
5 2
1 2
1 3
3 4
3 5
5 2
2 1
3 1
4 3
5 2
3 3
2 1
3 1
Output
3
-1
-1
Note

First test case

LCA of $$$4$$$ and $$$5$$$ is $$$3$$$.

LCA of $$$4$$$ and $$$2$$$ is $$$1$$$.

LCA of $$$5$$$ and $$$2$$$ is $$$1$$$.

The set $$$S$$$ is equal to {$$$1$$$, $$$3$$$}, which contains two elements.