Example

Input

5
1 2
1 3
1 4
1 5


Output

6
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define MOD 100000000000009LL
#define MAX_N 100010
typedef unsigned long long ull;
vector<ull>x[MAX_N], y[MAX_N]; vector<int>G;
ull dp[MAX_N]; queue<ull>Q; ull r[MAX_N];
bool used[MAX_N];
int main() {
	int n; cin >> n;
	for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; y[a].push_back(b); y[b].push_back(a); }
	Q.push(1LL); used[1] = true;
	while (!Q.empty()) {
		ull a1 = Q.front(); Q.pop(); G.push_back(a1);
		for (int i = 0; i < (int)y[a1].size(); i++) {
			if (used[y[a1][i]] == false) { used[y[a1][i]] = true; Q.push(y[a1][i]); }
		}
	}
	for (int i = 0; i < (int)G.size(); i++)r[G[i]] = i + 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (int)y[i].size(); j++) {
			x[r[i]].push_back(r[y[i][j]]);
		}
	}
	for (int i = n; i >= 1; i--) {
		ull sum = 0; int cnt2 = 0;
		for (int j = 0; j < (int)x[i].size(); j++) {
			if (i > x[i][j])continue;
			sum += dp[x[i][j]]; sum %= MOD; cnt2++;
		}
		dp[i] = (sum * 100009ULL + 1) % MOD;
	}
	sort(dp + 1, dp + n + 1); ull cnt = 0, cnt2 = 0;
	for (int i = 1; i <= n + 1; i++) {
		if (dp[i - 1] != dp[i]) { cnt += cnt2*(cnt2 - 1) / 2; cnt2 = 1; }
		else { cnt2++; }
	}
	cout << cnt << endl;
	return 0;
}