Tree Partitioning into Equal Connected Components

Given a tree with \(N\) nodes and an integer \(K\), determine whether it is possible to partition the tree into \(\frac{N}{K}\) connected components, each containing exactly \(K\) nodes.

A tree is a connected acyclic undirected graph. You are given \(N\) and \(K\) along with \(N-1\) edges that describe the tree. It is guaranteed that \(N\) is divisible by \(K\) if a valid partition exists. Otherwise, the answer is automatically NO.

Note: A valid partition is one in which every connected component (subtree) you obtain after removing some edges consists of exactly \(K\) nodes.

inputFormat

The first line contains two integers \(N\) and \(K\) (\(1 \leq N \leq 10^5\), \(1 \leq K \leq N\)).

The following \(N-1\) lines each contain two integers \(u\) and \(v\) (\(1 \leq u,v \leq N\)), representing an undirected edge between nodes \(u\) and \(v\).

outputFormat

Print a single line with the string YES if it is possible to partition the tree into connected components of exactly \(K\) nodes. Otherwise, print NO.

sample

6 3
1 2
2 3
3 4
4 5
5 6

YES