#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, k;
map<int, int> lost;
vector<vector<int>> adj, cutoff, depth;
void dfs(int u, int p, int d) {
depth[d].push_back(u);
if (d == k) {
lost[u] = lost.size();
cutoff[u] = {u};
return;
}
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u, d + 1);
cutoff[u].insert(cutoff[u].end(), cutoff[v].begin(), cutoff[v].end());
}
};
void solve() {
cin >> n >> k;
adj.resize(n), cutoff.resize(n), depth.resize(k + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v), adj[v].push_back(u);
}
if (k * k >= n) {
cout << "DA\n";
return;
}
dfs(0, 0, 0);
vector<pii> inter;
for (vector<int> &cc : cutoff) {
if (!cc.size()) {
inter.push_back({-1, -1});
} else {
inter.push_back({lost[cc.front()] + 1, lost[cc.back()] + 1});
}
}
vector<int> dp(1 << k);
dp[0] = 0;
for (int mask = 1; mask < (1 << k); mask++) {
int &curr = dp[mask];
for (int nxt = 0; nxt < k; nxt++) {
if (mask & (1 << nxt)) {
int pre = dp[mask & ~(1 << nxt)];
for (int n : depth[nxt + 1]) {
if (inter[n].first <= pre + 1) {
curr = max(curr, inter[n].second);
}
}
}
}
if (dp[mask] == lost.size()) {
cout << "DA\n";
return;
}
}
cout << "NE\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
