#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
if (k * k >= n) {
cout << "DA\n";
return 0;
}
vector<vector<int>> adjacency(n);
for (int i = 0; i < n - 1; ++i) {
int a, b; cin >> a >> b; --a; --b;
adjacency[a].push_back(b);
adjacency[b].push_back(a);
}
map<int, int> leafIndex;
vector<vector<int>> nodeAtDepths(k + 1);
vector<pair<int, int>> intervals(n, {n, -1});
function<void(int, int, int)> processTree;
processTree = [&](int cur, int prev, int depth) {
nodeAtDepths[depth].push_back(cur);
if (depth == k) {
leafIndex[cur] = leafIndex.size();
intervals[cur] = {leafIndex[cur], leafIndex[cur]};
return;
}
for (int &node : adjacency[cur]) {
if (node == prev) continue;
processTree(node, cur, depth + 1);
intervals[cur].first = min(intervals[cur].first, intervals[node].first);
intervals[cur].second = max(intervals[cur].second, intervals[node].second);
}
};
processTree(0, -1, 0);
vector<int> dp(1 << k, -1);
for (int i = 0; i < (1 << k); ++i) {
for (int j = 0; j < k; ++j) {
if (!(i & (1 << j))) continue;
int prev = dp[i ^ (1 << j)];
for (int &node : nodeAtDepths[j + 1]) {
if (intervals[node].first <= prev + 1) dp[i] = max(dp[i], intervals[node].second);
}
}
if (dp[i] == leafIndex.size() - 1) {
cout << "DA\n";
return 0;
}
}
cout << "NE\n";
return 0;
}
