#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 405;
const int MAXK = 20;
vector<int> adj[MAXN];
int n, k;
// --- Preprocessing variables ---
int depth[MAXN];
vector<int> nodes_at_depth[MAXN];
vector<int> leaves;
int leaf_idx_counter = 0;
pair<int, int> cover_range[MAXN]; // {min_leaf_idx, max_leaf_idx}
// --- DP table ---
// dp[mask] = max number of leaves covered consecutively from the start
int dp[1 << MAXK];
// DFS to calculate depth of each node
void dfs_depth(int u, int p, int d) {
depth[u] = d;
if (d < k) {
nodes_at_depth[d].push_back(u);
}
bool is_leaf_node = true;
for (int v : adj[u]) {
if (v == p) continue;
is_leaf_node = false;
dfs_depth(v, u, d + 1);
}
// A node is a leaf for our purpose if it's at depth k,
// or it's a true leaf of the tree at depth < k.
if (d < k && is_leaf_node) {
leaves.push_back(u);
}
if (d == k) {
leaves.push_back(u);
}
}
// DFS to order leaves and calculate the cover range for each node
void dfs_leaves(int u, int p) {
cover_range[u] = {n, -1}; // Initialize with invalid range
bool is_leaf_node = true;
for (int v : adj[u]) {
if (v == p) continue;
is_leaf_node = false;
dfs_leaves(v, u);
// Propagate child's cover range up to the parent
cover_range[u].first = min(cover_range[u].first, cover_range[v].first);
cover_range[u].second = max(cover_range[u].second, cover_range[v].second);
}
if (depth[u] < k && is_leaf_node) {
cover_range[u] = {leaf_idx_counter, leaf_idx_counter};
leaf_idx_counter++;
}
if (depth[u] == k) {
cover_range[u] = {leaf_idx_counter, leaf_idx_counter};
leaf_idx_counter++;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
// Handle the case proven by mathematical induction
if (k * k >= n) {
cout << "DA" << endl;
return 0;
}
// If k is large enough for the DP to be too slow, but the above check fails,
// it implies we can win. The threshold k=20 is safe.
if (k >= 20) {
cout << "DA" << endl;
return 0;
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// --- Preprocessing ---
dfs_depth(1, 0, 0);
// Sort leaves by their original node index to ensure a consistent order
sort(leaves.begin(), leaves.end());
// Re-map the leaf nodes to their 0-indexed order
vector<int> temp_leaves = leaves;
leaves.clear();
dfs_leaves(1, 0);
int num_leaves = leaf_idx_counter;
if (num_leaves == 0) { // If there are no leaves up to depth k, we win.
cout << "DA" << endl;
return 0;
}
// --- Bitmask DP ---
fill(dp, dp + (1 << k), -1);
dp[0] = -1; // Covers leaves up to index -1 (i.e., 0 leaves)
for (int mask = 0; mask < (1 << k); ++mask) {
if (dp[mask] == -1 && mask != 0) continue;
for (int d = 1; d <= k; ++d) {
// If we haven't placed a mark at depth 'd' yet
if (!((mask >> (d - 1)) & 1)) {
int new_mask = mask | (1 << (d - 1));
// Try placing a mark on each node 'u' at depth 'd'
for (int u : nodes_at_depth[d]) {
int min_l = cover_range[u].first;
int max_l = cover_range[u].second;
// If this node's cover range can extend our current contiguous coverage
if (min_l <= dp[mask] + 1) {
int new_coverage = max(dp[mask], max_l);
dp[new_mask] = max(dp[new_mask], new_coverage);
}
}
}
}
}
// --- Final Check ---
bool possible = false;
for (int mask = 0; mask < (1 << k); ++mask) {
// Count number of marks used (__builtin_popcount)
if (__builtin_popcount(mask) <= k) {
if (dp[mask] + 1 >= num_leaves) {
possible = true;
break;
}
}
}
if (possible) {
cout << "DA" << endl;
} else {
cout << "NE" << endl;
}
return 0;
}
