「CZYZOI 2017.04.24 JZ 03.08 C」 游戏

内存限制: 512 MiB 时间限制: 1000 ms
标准输入输出

题目描述

有一天小 AA 和小 BB 在一棵有 NN 个节点的树上玩游戏,初始时 11 号节点上有一枚硬币。游戏以如下方式进行:

●每一轮,小 AA 选取一个节点,并在该节点上画一个叉

●紧接着,小 BB 将硬币移动到一个相邻的、没有被画叉的节点

●小 BB 在硬币原来所在的节点上画一个叉

以上三步不停重复,直到小 BB 无法再移动硬币。

而在游戏过程中,小 AA 全程被戴上眼罩,因此小 AA 无法准确地知道每一个时刻硬币在哪一个节点上。

他只知道树的形态以及初始时硬币在哪一个节点上。

两盘游戏以后,小 AA 对这个游戏失去了兴趣。他想尽快结束游戏。

现在他想知道是否存在一种操作的方式,使得不管小 BB 如何操作,游戏都会在 KK 步以内结束(小 BB 移动硬币次数小于 KK 步)。

输入格式

第一行两个正整数,NNKK

接下来 N1N-1 行,每行两个正整数 A,B(1A,BN)A,B(1\le A,B\le N),表示在树中 AABB 相连。

数据保证给出的图是一棵树

输出格式

输出仅一行,“ DADA ”表示小 AA 可以保证游戏在 KK 步以内结束。“ NENE ”表示不能。

样例

输入样例1

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

输出样例1

DA

输入样例2

3 1
1 2
1 3

输出样例2

NE

输入样例3

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

输出样例3

DA

数据范围与提示

1KN4001\le K\le N\le 400