Burza

Time limit1sMemory limit512 MB

Summary

Given a tree and a blind pre-committed node-marking order, decide whether the coin can be forced to move fewer than K times regardless of the adversary's play.

Level: Hard8 of 10
Topics: Game theory, Tree, DFS, Greedy
Solved: No attempts yet

Problem

Daniel is tired of job hunting, so he went to visit his friend Stjepan. In Stjepan's home there is a tree with $N$ nodes numbered $1$ to $N$ , and a coin sits on node $1$ .

Stjepan put a blindfold on Daniel and explained the rules of the game.

Daniel picks a node and marks it.
Stjepan moves the coin to an unmarked node adjacent to the one the coin is on.
Stjepan marks the node the coin just left.

These three steps repeat until Stjepan can no longer move the coin. If at least one unmarked neighbour is left, Stjepan must move the coin.

Daniel is blindfolded, so during the game he never learns where the coin is. He only knows the shape of the tree and the starting node of the coin, which means he has to fix the whole order of the nodes he marks before the game starts.

Daniel wants to finish the game quickly and get back to sending out his resume. Decide whether he can choose an order of marks so that, no matter how Stjepan plays, the coin moves fewer than $K$ times, that is at most $K-1$ times.

Input

The first line contains the integers $N$ and $K$ . ( $1 \le K \le N \le 400$ )

Each of the next $N-1$ lines contains two integers $A$ and $B$ ( $1 \le A, B \le N$ ), meaning that an edge joins node $A$ and node $B$ .

The given graph is always a tree.

Output

Print DA on the first line if Daniel can make the coin move fewer than $K$ times no matter how Stjepan plays, and NE if he cannot. DA and NE are Croatian for yes and no. Do not print the quotation marks.

Examples3

Example 1
Input
```
6 2
1 2
2 3
3 4
1 5
5 6
```
Expected output
```
DA
```
Example 2
Input
```
3 1
1 2
1 3
```
Expected output
```
NE
```
Example 3
Input
```
8 2
1 2
2 3
2 4
5 6
6 8
1 5
7 1
```
Expected output
```
DA
```