2020 Mid-Atlantic USA Regional Contest

Start

2021-03-06 10:00 AKST

2020 Mid-Atlantic USA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -46 days 22:26:56

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
Kth Subtree

You are given an unrooted labeled tree. A subtree is a connected subgraph of this tree. The size of a subtree is the number of nodes in the subtree. Two subtrees are different if there is at least one node which is in one but not the other. The largest subtree is the original tree itself.

Compute the size of the $K^\mathrm {th}$ smallest non-empty subtree.

Input

The first line of input contains two integers $n$ ($1 \le n \le 5\, 000$) and $K$ ($1 \le K \le 10^{18}$), where $n$ is the number of nodes in the tree, and you’re looking for the size of the $K^{th}$ smallest subtree. The nodes are numbered $1$ through $n$.

Each of the next $n-1$ lines contains a pair of integers $u$ and $v$ ($1 \le u, v \le n, u \neq v$), which represents an undirected edge between nodes $u$ and $v$. All edges are distinct. It is guaranteed that the edges form a single tree.

Output

Output a single integer, which is the number of nodes in the $K^{th}$ smallest non-empty subtree of the input tree. If there are fewer than $K$ non-empty subtrees of the given tree, output $-1$.

Sample Input 1 Sample Output 1
2 1
1 2
1
Sample Input 2 Sample Output 2
2 3
1 2
2
Sample Input 3 Sample Output 3
5 10
1 2
2 3
3 4
4 5
3