COCI '16 Contest 2 #6 Burza

View as PDF

Submit solution


Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

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 résumé to companies he's never heard of.

Input Specification

The first line of input contains two integers, N and K (1 \leq K \leq N \leq 400).

Each of the following N - 1 lines contains two integers A and B (1 \leq A, B \leq 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.

Output Specification

The first and only line of output must contain the word DA (Croatian for yes), if Daniel can ensure that the game ends in at most K moves, and NE (Croatian for no) if he can't.

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

Explanation for Sample Output 2

Daniel can mark any node. If he marks node 1 or 2, Stjepan can move the coin to node 3, and if he marks node 3, Stjepan can move the coin to node 2.

Sample Input 3

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

Sample Output 3

DA

Explanation for Sample Output 3

In his first move, Daniel can mark node 2, and in the second move mark node 6. Wherever Stjepan moves the coin in his first move, he won't be able to make a second move.


Comments

There are no comments at the moment.