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$ 的节点标记为 $1$ 到 $S$，将 $B$ 的节点标记为 $1$ 到 $S$，使得：

• 它们的根节点标记相同。
• $A$ 中标记为 $x$ 和 $y$ 的节点之间有边相连，当且仅当 $B$ 中标记为 $x$ 和 $y$ 的节点之间有边相连。

则称这两棵树在结构上相同。否则，认为 $A$ 和 $B$ 在结构上不同。

输入格式

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

接下来的 $N - 1$ 行，每行包含两个空格分隔的整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)，描述了 $T$ 中连接节点 $u_i$ 和 $v_i$ 的一条边。注意 $T$ 以节点 $1$ 为根。

子任务

下表显示了 25 分的分布情况：

输出格式

输出他可能开始使用的 $D$ 的数量，如果两种可能性在结构上不同，则认为它们是不同的。

样例

输入格式 1

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

输出格式 1

1

说明

可以证明唯一的可能 $D$ 是：

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

在上图中，红色部分是作为装饰添加的，而绿色填充部分代表 $T$ 的初始状态。虚线表示连接装饰与树的边。

输入格式 2

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

2

说明

第一种 $D$ 的可能性是：

使用此 $D$，我们可以通过以下方式得到 $T$：

第二种 $D$ 的可能性是：

使用此 $D$，我们可以通过以下方式得到 $T$：