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 -446 days 11:05:33

5:00:00

0:00:00

# Problem KKth 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