题目描述

Daniel 和 Stjepan 在一棵含有 $n$ 个节点的树上做游戏，树上各节点的编号为 $1,2,\dots,n$。游戏开始时，$1$ 号节点上有一枚硬币。

游戏规则如下：

1. Daniel 选择一个节点，将其标记。
2. Stjepan 标记当前硬币所在的节点。
3. Stjepan 将硬币移至一个尚未标记且与当前所在的节点相邻的节点。

重复以上操作。当 Stjepan 无法移动硬币时，游戏结束。

Daniel 想知道是否存在某种既定的操作策略，使得无论 Stjepan 如何操作，都能在 $k$ 轮操作内结束游戏。即 Stjepan 能移动硬币的次数小于 $k$。

输入格式

第一行两个整数 $n,k$。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示编号为 $a,b$ 的结点间存在一条边。

输出格式

若存在满足条件的操作策略，输出一行 DA。

否则，输出一行 NE。

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

DA 

3 1
1 2
1 3 

NE 

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

DA 

提示

【样例解释】

样例 2 解释

• 若 Daniel 标记结点 $1$，Stjepan 可以将硬币移至结点 $2$ 或结点 $3$。
• 若 Daniel 标记结点 $2$，Stjepan 可以将硬币移至结点 $3$。
• 若 Daniel 标记结点 $3$，Stjepan 可以将硬币移至结点 $2$。

均不能在 $1$ 轮操作内结束游戏。

即不存在满足条件的操作策略。

样例 3 解释

• 第一轮操作，Daniel 标记结点 $2$。
• 第二轮操作，Daniel 标记结点 $6$。

无论 Stjepan 如何操作，都无法第二次移动硬币。

即存在满足条件的操作策略。

【数据规模与约定】

对于 $100\%$ 的数据，$1\le k\le n\le 400$，$1\le a,b\le n$。

【说明】

题目译自 COCI2016-2017 CONTEST #2 T6 Burza。