Example

Input

5
1 2
1 3
1 4
1 5


Output

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

const int P = 1e9 + 7;
const int N = 110000;

int modExp(int a, int n, int p) {
	int ret = 1;
	for (; n; n >>= 1, a = 1LL * a * a % p) if (n & 1) ret = 1LL * ret * a % p;
	return ret;
}

long long ret;

int dp[N], pw[N], qw[N];
map<int, int> H;

long long sum;

vector<int> adj[N];

void dfs(int u, int p) {
	dp[u] = dp[p] + 1;
	ret = (ret + pw[dp[u]]) % P;
	int ans = (P - ret) % P;
	for (int v : adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	ans = (ans + ret) * 1LL * qw[dp[u]] % P;
	sum += H[ans];
	H[ans]++;
}

int main() {
	ios_base::sync_with_stdio(0);
	int n; cin >> n;
	for (int i = 0; i <= n; i++) pw[i] = (i == 0 ? 1 : pw[i - 1] * 1LL * 999983) % P;
	for (int i = 0; i <= n; i++) qw[i] = modExp(pw[i], P - 2, P);
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dp[0] = -1;
	dfs(1, 0);
	cout << sum << endl;
	return 0;
}

