Example

Input

5
1 2
1 3
1 4
1 5


Output

6
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using ll = long long;
struct Graph {
    Graph(const int n)
    {
        edge.resize(n);
    }
    void addEdge(const int from, const int to)
    {
        edge[from].push_back(to);
    }
    vector<vector<int>> edge;
};

constexpr ll MOD1 = 1e9 + 7;
constexpr ll MOD2 = 1e9 + 9;
constexpr ll BASE1 = 1e6 + 7;
constexpr ll BASE2 = 1e6 + 9;
using P = pair<ll, ll>;
map<P, int> num;

P dfs(const Graph& g, const int s, vector<bool>& used)
{
    used[s] = true;
    P ans = {1, 1};
    for (const int to : g.edge[s]) {
        if (not used[to]) {
            const P sub = dfs(g, to, used);
            (ans.first += sub.first * BASE1) %= MOD1;
            (ans.second += sub.second * BASE2) %= MOD2;
        }
    }
    num[ans]++;
    return ans;
}

int main()
{
    int N;
    cin >> N;
    Graph g(N);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g.addEdge(a, b);
        g.addEdge(b, a);
    }
    vector<bool> used(N, false);
    dfs(g, 0, used);
    ll ans = 0;
    for (const auto& e : num) {
        const ll n = e.second;
        ans += (n * (n - 1)) / 2;
    }
    cout << ans << endl;
    return 0;
}

