Example

Input

5
1 2
1 3
1 4
1 5


Output

6
#include <bits/stdc++.h>
#define int long long
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define DEBUG(x) cerr << #x << " " << x << endl
using namespace std;
 
const int BASE = 100003;
const int MOD = 30743651146573LL;
 
int depth[100000];
 
vector<vector<int>> child;
int parent[100000];
 
void dfs(int v) {
  for(int u : child[v]) {
    depth[u] = depth[v] + 1;
    dfs(u);
  }
}
 
int hash_value[100000];
 
signed main() {
  memset(depth, -1, sizeof(depth));
  int N; cin >> N;
  child.resize(N);
  parent[0] = -1;
  REP(i,N-1) {
    int a, b; cin >> a >> b;
    --a, --b;
    parent[b] = a;
    child[a].push_back(b);
  }
  depth[0] = 0;
  dfs(0);
  vector<pair<int, int>> ord;
  REP(i,N) {
    ord.emplace_back(-depth[i], i);
  }
  sort(ord.begin(), ord.end());
  REP(i,N) {
    int v = ord[i].second;
    int h = 1;
    for(int u : child[v]) {
      h += hash_value[u] * BASE;
      h %= MOD;
    }
    hash_value[v] = h;
  }
  map<int, int> hash_count;
  REP(i,N) {
    hash_count[hash_value[i]]++;
  }
  int ans = 0;
  for(auto kv : hash_count) {
    ans += kv.second * (kv.second - 1) / 2;
  }
  cout << ans << endl;
}