Coin Game on a Tree

Daniel and Stjepan play a game on a tree with $n$ nodes numbered $1,2,\dots,n$. Initially, a coin is placed at node $1$. The game proceeds in rounds as follows:

1. Daniel marks a node (the choice is made by a predetermined strategy).
2. Stjepan marks the node where the coin currently is.
3. Stjepan then moves the coin to an adjacent node which is unmarked.

The process repeats until Stjepan cannot move the coin, i.e. when the current coin node has no unmarked neighbor. Daniel wants to know if there exists a predetermined marking strategy so that, no matter how Stjepan moves the coin, the total number of coin moves is less than $k$.

A key observation is that since the graph is a tree the coin’s path will be simple. If we fix an ordering (or ranking) of all nodes (except node $1$) corresponding to the rounds in which Daniel will mark them, then the coin will be forced to stop as soon as it reaches the first node (on its unique $1$–to–v path) that appears in the ordering. In other words, if the first marked node encountered along the coin–path appears in round $r$, then the coin would have moved exactly $r-1$ times. Daniel’s aim is to choose the ordering so that for every path starting at $1$, the first marked node appears among the first $(k)$ positions (so that the coin moves at most $k-1$ times).

It turns out that one may compute an optimal guaranteed (worst–case) coin–move count $f(1)$ by rooting the tree at node $1$ and defining for every node $v$ the value $f(v)$ recursively as follows:

• If $v$ is a leaf then $f(v)=0$.
• Otherwise, let $f(u)$ for each child $u$ (i.e. neighbor of $v$ other than its parent) be computed, and sort these values in non–increasing order. Then [ f(v) = \max_{0\le i<d} \Bigl{ i + f(u_i) \Bigr}, ] where $d$ is the number of children of $v$ and $u_i$ is the child with the $i$–th largest $f(\cdot)$ (with $i$ starting from $0$).

Daniel is guaranteed a winning strategy if and only if $f(1) < k$.

Given $n$, $k$, and the tree structure, determine whether Daniel can guarantee that the coin will move less than $k$ times, regardless of Stjepan’s moves.

Note: In the input the tree is given as $n-1$ edges. It is guaranteed that the given graph is a tree.

inputFormat

The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$), representing the number of nodes and the maximum allowed coin moves plus one, respectively.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) representing an edge between nodes $u$ and $v$.

The tree is guaranteed to be connected.

outputFormat

Output a single line containing either YES if Daniel has a winning strategy (i.e. he can guarantee that the coin moves fewer than $k$ times), or NO otherwise.

sample

2 1
1 2

YES