#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 5e5 + 10;
const ull C = 1145148441919;
int n, m, sz[N], Fa[N];
ll sum[N];
vector<ull> a, b;
vector<int> G[N];
vector<pair<ull, int>> pos;
map<ull, int> H, MP;
void add(int x, int y) {
    G[x].push_back(y);
}
ull f[N];
ull shift(ull x) {
    x ^= (x << 31);
    x ^= (x >> 7);
    x ^= (x << 24);
    x ^= (x >> 44);
    return x;
}
void dfs(int x, int fa) {
    f[x] = 1, sz[x] = 1;
    Fa[x] = fa;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs(y, x);
        f[x] *= shift(f[y] + C);
        sz[x] += sz[y];
        sum[x] += sum[y];
    }
    sum[x] += sz[x];
    return;
}
void DFS(int x, int fa) {
    for (auto y : G[x]) {
        if (y == fa) continue;
        b.push_back(f[y]);
        DFS(y, x);
    }
    return;
}
void DFS2(int x, int fa, int d) {
    H[f[x]]--;
    for (auto y : G[x]) {
        if (y == fa) continue;
        pos.push_back({y, d});
        DFS2(y, x, d + 1);
    }
    return;
}
int main() {
    freopen("Decorations.in", "r", stdin);
    freopen("Decorations.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        add(u, v), add(v, u); 
    }
    dfs(1, 0); int rt = 0;
    if (m == 1) {
        for (auto y : G[1]) if (!rt || sz[y] > sz[rt]) rt = y;
        for (auto y : G[1]) if (y != rt) a.push_back(f[y]);
        DFS(rt, 1); 
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        if (a.size() != b.size()) {
            cout << "0" << '\n';
            return 0;
        }
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != b[i]) {
                cout << "0" << '\n';
                return 0;
            } 
        }
        cout << "1" << '\n';
    } else if (n <= 5000) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (n - sum[i] == m && !MP.count(f[i])) {
                H.clear();
                for (int j = 1; j <= n; j++) H[f[j]]++;
                pos.clear(); DFS2(i, Fa[i], 1); bool flag = 0;
                for (auto u : pos) {
                    if (H[f[u.first]] < u.second) {
                        flag = 1; break;
                    } else {
                        H[f[u.first]] -= u.second;
                    }
                }
                if (!flag) {
                    MP[f[i]] = 1;
                    ans++;
                }
            }
        }
        cout << ans << '\n';
    } else {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (n - sum[i] == m && !MP.count(f[i])) {
                ans++; MP[f[i]] = 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}