Example

Input

5
1 2
1 3
1 4
1 5


Output

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

using ll = long long;

constexpr ll base = 211;
constexpr ll M = 1000000000000037LL;

ll dfs(int v, vector<vector<int>>& g, vector<bool>& visited, vector<ll>& hs) {
    visited[v] = true;
    ll res = 1;
    for(auto to : g[v]) {
        if(!visited[to]) {
            (res += dfs(to, g, visited, hs) * base) %= M;
        }
    }
    return hs[v] = res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    for(int i=0; i<N-1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<bool> visited(N);
    vector<ll> hs(N);
    dfs(0, g, visited, hs);
    ll res = 0;
    sort(hs.begin(), hs.end());
    for(int i=0; i<N; ++i) {
        auto p = equal_range(hs.begin(), hs.end(), hs[i]);
        res += p.second - p.first - 1;
    }
    res /= 2;
    cout << res << endl;
} 
