#include <iostream>
#include <vector>
using namespace std;
int N, K;
vector<vector<int>> adjList, nodosPorProfundidad;
vector<int> hojas, hojaIzq, hojaDer, DP;
vector<bool> visitado;
/*
Hacemos una dfs para calcular, para cada nodo con profundidad <= k:
- su profundidad, añadiéndolo a nodosPorProfundidad en la capa correspondiente
- si su profundidad es K, lo añadiremos a nuestra lista de hojas
- hojasIzq[nodo]: el índice dentro de la lista de hojas (empezando con 1) de la hoja más
a la izquierda en el subárbol de nodo
- hojasDer[nodo]: el índice dentro de la lista de hojas (empezando con 1) de la hoja más
a la derecha en el subárbol de nodo
*/
void dfs(int nodo, int profundidad) {
visitado[nodo] = true;
if (profundidad == K) {
hojas.push_back(nodo);
nodosPorProfundidad[profundidad].push_back(nodo);
hojaIzq[nodo] = (int) hojas.size();
hojaDer[nodo] = (int) hojas.size();
return;
}
nodosPorProfundidad[profundidad].push_back(nodo);
for (int vecino: adjList[nodo]) {
if (!visitado[vecino]) {
dfs(vecino, profundidad+1);
hojaIzq[nodo] = min(hojaIzq[nodo], hojaIzq[vecino]);
hojaDer[nodo] = max(hojaDer[nodo], hojaDer[vecino]);
}
}
}
/*
DP[mascara] guarda, quitando un nodo en cada capa de la máscara, la longitud del máximo
prefijo de hojas que podremos cubrir.
Dada una máscara, probamos a quitar de cada capa incluida cada nodo incluido.
Miramos el valor de la DP en esa máscara sin la capa quitada y vemos si la unión
de ese valor y las hojas cubiertas por el nodo quitado aumenta el récord actual,
en cuyo caso lo actualizamos.
*/
int calcDP(int mascara) {
if (DP[mascara] != -1) return DP[mascara];
int ans = 0;
for (int i = 0; i < K; i++) {
if (mascara & (1<<i)) {
int mascaraVieja = mascara - (1<<i);
int dpVieja = calcDP(mascaraVieja);
ans = max(ans, dpVieja);
for (int nodo: nodosPorProfundidad[i+1]) {
if (hojaIzq[nodo]-1 <= dpVieja) ans = max(ans, hojaDer[nodo]);
}
}
}
return DP[mascara] = ans;
}
bool esPosible() {
visitado.assign(N, false);
hojaIzq.assign(N, N);
hojaDer.assign(N, -1);
nodosPorProfundidad.assign(K+1, vector<int>());
dfs(0, 0);
int numHojas = (int) hojas.size();
DP.assign(1<<K, -1);
DP[0] = 0;
return calcDP((1<<K) - 1) == numHojas;
}
int main() {
cin >> N >> K;
adjList = vector<vector<int>>(N);
int A, B;
for (int i = 0; i < N-1; i++) {
cin >> A >> B;
adjList[A-1].push_back(B-1);
adjList[B-1].push_back(A-1);
}
if (K*K >= N || esPosible()) cout << "DA\n";
else cout << "NE\n";
return 0;
}
