1 \(s / 512\) \(MB / 160\) points

Daniel is tired of looking for a job, so he decided to visit his friend Stjepan. Surprisingly,
when he entered Stjepan’s home, he came across a tree with \(N\)

nodes denoted with
numbers from 1 to \(N\)

. The node number 1 contains a coin.

Stjepan told him: “ Put this blindfold on and we’ll play!

” Daniel gave him a strange look, but
decided to do it. Stjepan then told him the rules of the game:
●
Daniel picks a node and marks it
●
Stjepan moves the coin to an unmarked node adjacent to the one where the
coin is currently in
●
Stjepan marks the node which he moved the coin from

These three steps repeat until Stjepan can’t make a move anymore. Given the fact that he is
blindfolded, Daniel doesn’t exactly know what node contains the coin in any given moment of
the game. However, he does know the outline of the tree and where the coin was at the
beginning of the game.

Daniel just realized that he hasn’t applied to a single job for the past two hours, and wants to
quickly finish playing the game. Now he wants to know if he can play in a way that, no
matter what moves Stjepan makes , the game ends in at most k moves . In other words,
so that Stjepan moves the coin less than k times .

Help Daniel and determine whether he can finish the game on time and go back to sending
his resume to companies he’s never heard of.

The first line of input contains two integers, \(N\)

and K.

(1 ≤ \(K\)

≤ \(N\)

≤ 400)
Each of the following \(N - 1\)

lines contains two integers \(A\)

and \(B\)

(1 ≤ A, B

≤ \(N\)

) that denote
that an undirected link exists between nodes labeled with \(A\)

and \(B\)

.
It is guaranteed that the given graph will be a tree.

The first and only line of output must contain the word “DA” (Croatian for yes), without
quotation marks, if Daniel can ensure that the game ends in at most \(K\)

moves, and “NE”
(Croatian for no) if he can’t.

1 \(s / 512\) \(MB / 160\) points

생성자가 기록되지 않았습니다.

출처 COCI 2016/2017 Contest 2