#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
double chance = 0, multi = 0.99992;
int fdep (int i, int f, vector<vector<int>> &adj, vector<int> &dep) {
int mx = dep[i];
for (int j: adj[i]) {
if (j == f) continue;
dep[j] = dep[i]+1;
mx = max(mx, fdep(j, i, adj, dep));
}
return mx;
}
int dfs (int i, int f, int k, int d, vector<vector<int>> &adj, vector<bool> &alive) {
if (!alive[i]) return 0;
if (d >= k) return 1;
int ans = 0;
for (int j: adj[i]) if (j != f) ans += dfs(j, i, k, d+1, adj, alive);
return ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<vector<int>> adj(n);
for (int a, b, i = 1; i < n; i++) {
cin >> a >> b;
adj[--a].push_back(--b);
adj[b].push_back(a);
}
vector<int> dep(n, 0);
int md = fdep(0, 0, adj, dep);
k = min(k, md);
vector<vector<int>> atd(k);
for (int i = 0; i < n; i++) if (dep[i] && dep[i] <= k) atd[dep[i]-1].push_back(i);
vector<int> ptr(k, 0);
vector<bool> alive(n, 1);
for (int i = 0; i < k; i++) alive[atd[i][0]] = 0;
int sc = dfs(0, 0, k, 0, adj, alive);
mt19937 mt(time(NULL));
for (auto t = chrono::steady_clock::now(); chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now()-t).count() < 990; chance *= multi) {
if (!sc) return cout << "DA\n", 0;
vector<pair<int, int>> mv;
for (int eui = 1; eui <= 6; eui++) {
if (mt()%2 || eui == 6) {
for (int aoe = 0; aoe < eui; aoe++) {
int f = mt()%k;
alive[atd[f][ptr[f]]] = 1;
int b = ptr[f];
ptr[f] = mt()%atd[f].size();
alive[atd[f][ptr[f]]] = 0;
mv.push_back({f, b});
}
}
}
int nw = dfs(0, 0, k, 0, adj, alive);
if (nw <= sc || chance*(double)sc/(double)nw < (double)mt()/(double)(long long)mt.max) {
sc = nw;
continue;
}
while (mv.size()) {
int f = mv.back().f, b = mv.back().s;
mv.pop_back();
alive[atd[f][ptr[f]]] = 1;
ptr[f] = b;
alive[atd[f][b]] = 0;
}
}
cout << "NE\n";
}
