Description

Daniel and Stjepan are playing a game on a tree with $n$ nodes, where the nodes are numbered $1,2,\dots,n$. At the start of the game, there is a coin on node $1$.

The rules are as follows:

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

Repeat the above steps. When Stjepan cannot move the coin, the game ends.

Daniel wants to know whether there exists a fixed strategy such that, no matter how Stjepan plays, the game can be ended within $k$ rounds. That is, the number of times Stjepan can move the coin is less than $k$.

Input Format

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

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

Output Format

If there exists a strategy that satisfies the condition, output one line DA.

Otherwise, output one line 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 

Hint

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$.

In all cases, the game cannot be ended within $1$ round.

So, there is no strategy that satisfies the condition.

Sample 3 Explanation

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

No matter how Stjepan plays, he cannot move the coin for the second time.

So, there exists a strategy that satisfies the condition.

Constraints

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

Notes

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

Translated by ChatGPT 5