P6499 [COCI 2016/2017 #2] Burza

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

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

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

#### 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](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #2](https://hsin.hr/coci/archive/2016_2017/contest2_tasks.pdf) _T6 Burza_.** Translated by ChatGPT 5