// time-limit: 3000
#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
#define ll long long
using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;
void setIO(string name = "") {
if (name.size()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void solve() {
return;
}
unordered_map<int, vi> m;
unordered_map<int, vi> depths;
vector<pair<int,int> > ints; // intervals that each node covers
int bi = 0;
int k = 0;
pair<int,int> mergep(pair<int,int> &p1, pair<int,int> &p2) {
if (p1.first == 0 && p1.second == 0) return p2;
return make_pair(min(p1.first, p2.first), max(p1.second, p2.second));
}
void dfs(int x, int prev, int depth) {
depths[depth].push_back(x);
if (depth == k) {
bi++;
ints[x] = make_pair(bi,bi);
return;
}
for (auto &e: m[x]) {
if (e != prev) {
dfs(e, x, depth+1);
ints[x] = mergep(ints[x], ints[e]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// setIO("test");
// if k^2 >= n, then game can end.
// at step i, delete a node at depth i
// if we cut off largest subtree at every step,
// tr is number of valid nodes with depth r+1
// nr is the number of valid nodes at step r
// nr+1 <= nr - nr/tr - (tr - 1)
// nr/tr is the largest subtree
// nodes with depth r are also removed
// at 1 node at depth r from that largest subtree that was removed
// to avoid double count
//
int n;
cin >> n >> k;
ints.resize(n+1);
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
m[a].push_back(b);
}
if (k * k >= n) {
cout << "DA" << endl;
return 0;
}
// dfs to leaf nodes (when depth == k)
// assign new leaf nodes a new index,
// leaf node's own interval is [index, index]
// then update intervals of parents
// store node depths too
//
// bitwise dp[s] = n,
// s&(1<<i) means a node at depth i is in subset
// where subset can cover leaves 1...n
// if s&(1<<i) s^(1<<i) and merge with interval of node j, for all node j at depth i
dfs(1, -1, 0);
vi dp(1<<(k+1));
for (int s = 0; s < 1<<k; s++) {
for (int i = 0; i < k; i++) {
if (s&(1<<i)) {
dp[s] = max(dp[s], dp[s^(1<<i)]);
for (auto &e: depths[i+1]) {
if (ints[e].first <= dp[s^(1<<i)]+1) dp[s] = max(dp[s], ints[e].second);
}
}
}
}
cout << (dp[(1<<k)-1] == bi ? "DA" : "NE") << endl;
return 0;
}
