Problem Description

Daniel and Stjepan are playing a game on a tree with $n$ nodes, where each node is numbered from $1$ to $n$. At the start of the game, a coin is placed on node $1$.

The rules of the game are as follows:

1. Daniel selects a node and marks it.
2. Stjepan marks the node where the coin is currently located.
3. Stjepan moves the coin to an unmarked node that is adjacent to the current node.

This process is repeated. The game ends when Stjepan cannot move the coin anymore.

Daniel wants to know if there exists a predetermined strategy such that, regardless of Stjepan's moves, the game can end within $k$ rounds. In other words, Stjepan can move the coin fewer than $k$ times.

Input Format

The first line contains two integers $n$ and $k$.

The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between nodes $a$ and $b$.

Output Format

If there exists a strategy that meets the conditions, output one line containing DA.

Otherwise, output one line containing NE.

Sample Input and Output

Sample Input #1

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

Sample Output #1

DA

Sample Input #2

3 1
1 2
1 3

Sample Output #2

NE

Sample Input #3

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

Sample Output #3

DA

Notes

Sample Explanation

Sample 2 Explanation

• If Daniel marks node $1$, Stjepan can move the coin to node $2$ or node $3$.
• If Daniel marks node $2$, Stjepan can move the coin to node $3$.
• If Daniel marks node $3$, Stjepan can move the coin to node $2$.

None of these scenarios allow the game to end within one round.

Thus, there is no strategy that meets the conditions.

Sample 3 Explanation

• In the first round, Daniel marks node $2$.
• In the second round, Daniel marks node $6$.

Regardless of Stjepan's moves, he cannot move the coin a second time.

Thus, there is a strategy that meets the conditions.

Data Constraints

For $100\%$ of the data, $1 \le k \le n \le 400$, and $1 \le a, b \le n$.

Notes

This problem is translated from COCI2016-2017 CONTEST #2 T6 Burza.

见题面 Input 部分

见题面 Output 部分