#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
if(!(cin >> N >> K)) return 0;
vector<vector<int>> adj(N+1);
for(int i=0;i<N-1;i++){
int A,B; cin >> A >> B;
adj[A].push_back(B);
adj[B].push_back(A);
}
// 1) depth from root 1
vector<int> depth(N+1, -1), parent(N+1, -1);
queue<int>q;
depth[1]=0; parent[1]=0; q.push(1);
while(!q.empty()){
int u=q.front(); q.pop();
for(int v: adj[u]){
if(depth[v]==-1){
depth[v]=depth[u]+1;
parent[v]=u;
q.push(v);
}
}
}
// if no node at depth >= K -> Daniel trivially wins
bool anyDepthGEK = false;
for(int i=1;i<=N;i++) if(depth[i] >= K) { anyDepthGEK = true; break; }
if(!anyDepthGEK){
cout << "DA\n";
return 0;
}
// fast condition from editorial: if K*K >= N -> DA
if(1LL*K*K >= N){
cout << "DA\n";
return 0;
}
// Now K is small (<= ~19). Build rooted tree children lists (using parent)
vector<vector<int>> children(N+1);
for(int v=2; v<=N; ++v){
int p = parent[v];
if(p!=-1) children[p].push_back(v);
}
// hasLeaf[v] := exists descendant at depth == K
vector<char> hasLeaf(N+1, 0);
function<void(int)> dfs_has = [&](int u){
bool hl = (depth[u] == K);
for(int v: children[u]){
dfs_has(v);
hl = hl || hasLeaf[v];
}
hasLeaf[u] = hl;
};
dfs_has(1);
// Build pruned tree: keep nodes with depth <= K and hasLeaf==true
vector<char> keep(N+1, 0);
for(int i=1;i<=N;i++){
if(depth[i] <= K && hasLeaf[i]) keep[i] = 1;
}
// If root gets removed (shouldn't since some node depth==K exists), handle
if(!keep[1]){
cout << "DA\n";
return 0;
}
// Rebuild childrenPruned
vector<vector<int>> childP(N+1);
for(int u=1;u<=N;u++){
if(!keep[u]) continue;
for(int v: children[u]){
if(keep[v]) childP[u].push_back(v);
}
}
// Assign leaf indices (leaves are nodes with depth == K and kept)
int leafCnt = 0;
vector<int> L(N+1, INT_MAX), R(N+1, -1);
function<void(int)> dfs_leaves = [&](int u){
if(depth[u] == K){
// a leaf in pruned tree
L[u] = R[u] = leafCnt++;
}
for(int v: childP[u]){
dfs_leaves(v);
if(L[v] < L[u]) L[u] = L[v];
if(R[v] > R[u]) R[u] = R[v];
}
// nodes that are internal but have no kept descendants shouldn't exist due to hasLeaf
// but keep safe: if untouched, make L>R meaning no leaves below
};
dfs_leaves(1);
if(leafCnt == 0){
// no depth==K nodes after pruning => trivial win
cout << "DA\n";
return 0;
}
// Collect intervals per depth (depth 1..K). We will only consider nodes with depth in [1..K]
// Each such node covers a contiguous interval of leaves [L[u], R[u]].
// If L[u] == INT_MAX then it covers nothing (ignore).
int maxD = K;
vector<vector<pair<int,int>>> byDepth(maxD+1);
for(int u=1; u<=N; ++u){
if(!keep[u]) continue;
int d = depth[u];
if(d >= 1 && d <= K && L[u] != INT_MAX && L[u] <= R[u]){
byDepth[d].push_back({L[u], R[u]});
}
}
// Bitmask DP: dp[mask] = maximum prefix (number of initial leaves covered) achievable using depths in mask
int maxMask = 1<<K; // K < ~20 so OK
const int NEG = -1000000;
vector<int> dp(maxMask, NEG);
dp[0] = 0;
for(int mask=0; mask<maxMask; ++mask){
if(dp[mask] < 0) continue;
if(dp[mask] >= leafCnt){
cout << "DA\n";
return 0;
}
// try to add a depth not yet used
for(int d=1; d<=K; ++d){
int bit = 1 << (d-1);
if(mask & bit) continue;
int cur = dp[mask];
int best = dp[mask | bit];
// try all nodes at this depth
for(auto &iv : byDepth[d]){
int Luv = iv.first, Ruv = iv.second;
if(Luv <= cur){ // we can attach this interval to current prefix
int newCov = max(cur, Ruv + 1); // covers up to Ruv inclusive -> prefix length Ruv+1
if(newCov > best) best = newCov;
}
}
dp[mask | bit] = best;
}
}
// check final
bool ok = false;
for(int mask=0; mask<maxMask; ++mask){
if(dp[mask] >= leafCnt){ ok = true; break; }
}
cout << (ok ? "DA\n" : "NE\n");
return 0;
}
