有人给伊万一份奇怪的生日礼物。它是刺猬——连通无向图,其中一个顶点的度数至少为 $$$3$$$(我们将其称为中心),而所有其他顶点的度数为 1。 Ivan 认为刺猬太无聊,决定让自己成为 $$$k$$$-multihedgehog。
让我们定义 $$$k$$$-multihedgehog 如下:
- $$$1$$$-multihedgehog 是刺猬:它有一个度数至少为 $$$3$$$ 的顶点和一些度数为 1 的顶点。
- 对于所有 $$$k \ge 2$$$,$$$k$$$-multihedgehog 是 $$$(k-1)$$$-multihedgehog,其中对度数为 1 的每个顶点 $$$v$$$ 进行了以下更改:让 $$$u$$$ 成为其唯一邻居;删除顶点 $$$v$$$,创建一个以顶点 $$$w$$$ 为中心的新刺猬,并用边连接顶点 $$$u$$$ 和 $$$w$$$。新刺猬彼此之间以及最初的礼物可能有所不同。
因此 $$$k$$$-multihedgehog 是一棵树。 Ivan 制作了 $$$k$$$-multihedgehog,但他不确定自己没有犯任何错误。这就是为什么他要求你检查他的树是否确实是$$$k$$$-multihedgehog。
输入
输入的第一行包含 $$$2$$$ 整数 $$$n$$$, $$$k$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le k \le 10^{9}$$$) — 顶点数和刺猬参数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ $$$v$$$ ($$$1 \le u, \,\, v \le n; \,\, u \ne v$$$) — 由边连接的顶点的索引。
保证给定的图是一棵树。
输出
如果给定图形是 $$$k$$$-multihedgehog,则打印“是”(不带引号),否则打印“否”(不带引号)。
示例
输入 #1
14 2 1 4 2 4 3 4 4 13 10 5 11 5 12 5 14 5 5 13 6 7 8 6 13 6 9 6
输出 #1
Yes
输入 #2
3 1 1 3 2 3
输出 #2
No
注意
第一个示例中的 2-multihedgehog 如下所示:
其中心是顶点 $$$13$$$。最后一步创建的刺猬是:[4(中心)、1、2、3]、[6(中心)、7、8、9]、[5(中心)、10、11、12、13]。
第二个示例中的树不是刺猬,因为中心度应至少为 $$$3$$$。