Problem Description

Translated from CEOI2021 Day2 T3. Wells.

This problem has incomplete data, it is recommended to submit on loj: https://loj.ac/p/3597.

Problem Description

Given a tree with $N$ nodes and a positive integer $K$, determine if there exists a subset of vertices such that every path of exactly $K$ vertices contains exactly one vertex from this subset. Additionally, you need to find the number of such subsets modulo $10^9+7$ (if none exist, output $0$).

Input Format

The first line contains two integers $N$ and $K$.

The next $N-1$ lines each contain two integers $u$ and $v$, indicating an undirected edge between node $u$ and node $v$.

Output Format

The first line should contain a string, either YES if such a subset exists, or NO if it does not.

The second line should contain an integer, the number of subsets that meet the condition, or $0$ if no such subsets exist.

Sample Input and Output

Sample Input #1

4 2
3 4
3 1
2 3

Sample Output #1

YES
2

Sample Input #2

8 3
7 3
1 3
7 8
5 1
4 6
7 2
3 6

Sample Output #2

NO
0

Sample Input #3

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

Sample Output #3

YES
10

Notes

Sample Explanation 1

The subsets that meet the condition are: $\{3\}$ and $\{1,2,4\}$.

Sample Explanation 2

Sample Explanation 3

There is only one path of length $5$, which includes nodes $3,6,4,2,5$. Exactly one of these nodes must be in the subset, and whether node $1$ is in the subset does not matter.

Thus, all subsets that meet the condition are: $\{3\}$, $\{1,3\}$, $\{6\}$, $\{1,6\}$, $\{4\}$, $\{1,4\}$, $\{2\}$, $\{1,2\}$, $\{5\}$, $\{1,5\}$.

Data Range and Constraints

For $100\%$ of the data: $2\leq K\leq N\le 1.5\times 10^6$.

见题面 Input 部分

见题面 Output 部分