#include <bits/stdc++.h>
using namespace std;
//====== BITWISE ======//
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ON(x, i) ((x) | MASK(i))
#define OFF(x, i) ((x) & ~MASK(i))
#define LASTBIT(mask) ((mask) & -(mask))
#define SUBMASK(sub, mask) for (int sub = (mask); sub >= 1; sub = (sub - 1) & (mask))
//====== OTHER ======//
#define fi first
#define se second
#define ll long long
#define endl '\n'
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mod(x, k) ((((x) % (k)) + (k)) % (k))
#define compress(c) sort(all(c)); c.erase(unique(all(c)), c.end());
#define Longgggg ios_base::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
//====== FILE ======//
#define IN "A.in"
#define OUT "A.out"
#define DEBUG "debug.out"
//==================//
const int INF = (int) 1e9+5;
const ll LINF = (ll) 1e18;
const ll MOD = (ll) 1e9+7;
const int mxN = (int) 1e5+5;
int n, k;
vector <int> adj[mxN], nodesAtDepth[mxN];
vector <pair <int, int>> coveredInterval(mxN, {-1, -1});
int leafCnt = 0;
void dfs(int u, int pre, int d) {
if (d > k) return;
nodesAtDepth[d].push_back(u);
if (d == k) {
coveredInterval[u] = {leafCnt, leafCnt};
++leafCnt;
return;
}
int L = INF, R = -INF;
for (auto &v : adj[u]) {
if (v == pre) continue;
dfs(v, u, d+1);
pair <int, int> seg = coveredInterval[v];
if (seg.fi != -1) {
L = min(L, seg.fi);
R = max(R, seg.se);
}
}
if (R != -INF) coveredInterval[u] = {L, R};
}
void solve() {
cin >> n >> k;
FOR(i, 1, n-1) {
int u, v; cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if (1LL * k * k >= n) {
cout << "DA\n";
return;
}
dfs(0, -1, 0);
int numLeafK = leafCnt;
if (numLeafK == 0) {
cout << "DA\n";
return;
}
vector <int> dp(MASK(k), -1);
dp[0] = 0;
FOR(mask, 1, MASK(k)-1) {
int best = -1;
FOR(d, 0, k-1) if (BIT(mask, d)) {
int lst = OFF(mask, d);
if (dp[lst] == -1) continue;
for (auto &u : nodesAtDepth[d+1]) {
auto seg = coveredInterval[u];
if (seg.fi == -1) continue;
if (seg.fi <= dp[lst]) {
best = max(best, max(dp[lst], seg.se+1));
}
}
}
dp[mask] = best;
if (dp[mask] == leafCnt) {
cout << "DA\n";
return;
}
}
cout << "NE\n";
}
signed main() {
if (fopen(IN, "r")) {
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
freopen(DEBUG, "w", stderr);
}
Longgggg
ll t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
