Description

Mateo 最近为他的圣诞树找到了完美的装饰品——更多的树！

具体来说，他的圣诞树是一棵初始有 $M$ 个节点、全部涂成绿色的有根树 $T$。他还有另一棵用作装饰参考的有根树 $D$。Mateo 通过以下步骤完成所有装饰：

• 对于 $D$ 中的每个节点 $i$，他创建一份以 $i$ 为根的子树副本，记为 $C_i$。然后，他将 $C_i$ 的所有节点涂成红色。最后，他选择 $T$ 中的某个绿色节点作为 $C_i$ 根节点的父节点，并通过一条边将它们连接起来。

完成所有装饰后，$T$ 最终包含 $N$ 个节点。不幸的是，他忘记记录 $D$ 的具体形态了！更糟的是，他不小心将水洒在 $T$ 上，导致所有节点的颜色都被洗掉了。之后，他将 $T$ 的根节点标记为 1，其余节点依次标记为 2 到 $N$。

目前他唯一掌握的信息是 $T$ 的最终形态以及 $M$ 的值。请帮助他计算可能的初始树 $D$ 的数量（若两棵树结构不同，则视为不同的可能性）。

若两棵有根树 $A$ 和 $B$ 满足以下条件，则称它们是结构相同的：

• 节点数 $S$ 相同；
• 存在一种对 $A$ 和 $B$ 的节点分别从 1 到 $S$ 的标号方式，使得：
  • 它们的根节点标号相同；
  • $A$ 中标号为 $x$ 和 $y$ 的节点之间有边当且仅当 $B$ 中标号为 $x$ 和 $y$ 的节点之间有边。

否则，$A$ 和 $B$ 被视为结构不同。

Input Format

第一行输入包含两个以空格分隔的整数 $N$ 和 $M$。

接下来的 $N - 1$ 行，每行包含两个以空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq N$，$u_i \neq v_i$），表示 $T$ 中连接节点 $u_i$ 和 $v_i$ 的一条边。

Output Format

输出可能的初始树 $D$ 的数量（结构不同的树视为不同情况）。

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

1

14 5
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
2 10
10 11
10 12
10 13
10 14

2

Hint

样例 1 解释

可以证明，唯一可能的 $D$ 如下图所示：

通过以下方式可以得到 $T$：

上图中，红色部分为添加的装饰，绿色填充部分表示 $T$ 的初始状态，虚线表示连接装饰品的边。

样例 2 解释

第一种可能的 $D$：

通过以下方式可以得到 $T$：

第二种可能的 $D$：

通过以下方式可以得到 $T$：

以下表格展示了 25 分的分布情况：

翻译由 DeepSeek V3 完成