Example

Input

5
1 2
1 3
1 4
1 5


Output

6
#include<bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> edge;
vector<int> par;
vector<int> h;
int geth(int p, int pr) {
    par[p] = pr;
    int ma = 0;
    for (int i : edge[p]) {
        if (i == pr) continue;
        ma = max(ma, geth(i, p) + 1);
    }
    return h[p] = ma;
}

int main() {
    long long M = 1000007;
    cin >> n;
    edge.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    h.resize(n, -1);
    par.resize(n, -1);
    geth(0, -1);
    vector<vector<int>> lis(n);
    for (int i = 0; i < n; ++i) {
        lis[h[i]].push_back(i);
    }
    vector<long long> hsh(n, 0);
    vector<map<long long, long long>> hsmp(n);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j : lis[i]) {
            hsh[j] = 1;
            for (int k : edge[j]) {
                if (par[j] == k) continue;
                hsh[j] += hsh[k] * M;
            }
            if (hsmp[i].count(hsh[j]))
                ++hsmp[i][hsh[j]];
            else
                hsmp[i][hsh[j]] = 1;
        }
        for (auto& j : hsmp[i]) {
            ans += j.second * (j.second - 1) / 2;
        }
    }
    cout << ans << "\n";
    return 0;
}