During the chemistry lesson Andrew learned that the saturated hydrocarbons (alkanes) enter into radical chlorination reaction. Andrew is a very curious boy, so he wondered how many different products of the reaction may be forms for a given alkane. He managed to solve the task for small molecules, but for large ones he faced some difficulties and asks you to help.

Formally, you are given a tree consisting of n vertices, such that the degree of each vertex doesn't exceed 4. You have to count the number of distinct non-isomorphic trees that can be obtained by adding to this tree one new vertex and one new edge, such that the graph is still the tree and the degree of each vertex doesn't exceed 4.

Two trees are isomorphic if there exists a bijection f(v) such that vertices u and v are connected by an edge if and only if vertices f(v) and f(u) are connected by an edge.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the number of vertices in the tree.

Then follow n - 1 lines with edges descriptions. Each edge is given by two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of vertices connected by an edge. It's guaranteed that the given graph is a tree and the degree of each vertex doesn't exceed 4.

Output

Print one integer — the answer to the question.

Examples

Input

4
1 2
2 3
2 4


Output

2


Input

5
1 2
1 3
1 4
1 5


Output

1


Input

5
2 5
5 3
4 3
4 1


Output

3

Note

In the first sample, one can add new vertex to any existing vertex, but the trees we obtain by adding a new vertex to vertices 1, 3 and 4 are isomorphic, thus the answer is 2.

In the second sample, one can't add new vertex to the first vertex, as its degree is already equal to four. Trees, obtained by adding a new vertex to vertices 2, 3, 4 and 5 are isomorphic, thus the answer is 1.
#include <bits/stdc++.h>
using namespace std;
struct edge {
  long long to, cost;
  edge() {}
  edge(long long a, long long b) { to = a, cost = b; }
};
const long long dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
const long long mod = 1000000007;
struct mint {
  long long x = 0;
  mint(long long y = 0) {
    x = y;
    if (x < 0 || x >= mod) x = (x % mod + mod) % mod;
  }
  mint(const mint &ope) { x = ope.x; }
  mint operator-() { return mint(-x); }
  mint operator+(const mint &ope) { return mint(x) += ope; }
  mint operator-(const mint &ope) { return mint(x) -= ope; }
  mint operator*(const mint &ope) { return mint(x) *= ope; }
  mint operator/(const mint &ope) { return mint(x) /= ope; }
  mint &operator+=(const mint &ope) {
    x += ope.x;
    if (x >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint &ope) {
    x += mod - ope.x;
    if (x >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint &ope) {
    x *= ope.x, x %= mod;
    return *this;
  }
  mint &operator/=(const mint &ope) {
    long long n = mod - 2;
    mint mul = ope;
    while (n) {
      if (n & 1) *this *= mul;
      mul *= mul;
      n >>= 1;
    }
    return *this;
  }
  mint inverse() { return mint(1) / *this; }
  bool operator==(const mint &ope) { return x == ope.x; }
  bool operator!=(const mint &ope) { return x != ope.x; }
};
mint modpow(mint a, long long n) {
  if (n == 0) return mint(1);
  if (n % 2)
    return a * modpow(a, n - 1);
  else
    return modpow(a * a, n / 2);
}
istream &operator>>(istream &is, mint &ope) {
  long long t;
  is >> t, ope.x = t;
  return is;
}
ostream &operator<<(ostream &os, mint &ope) { return os << ope.x; }
ostream &operator<<(ostream &os, const mint &ope) { return os << ope.x; }
bool exceed(long long x, long long y, long long m) { return x >= m / y + 1; }
void mark() { cout << "*" << endl; }
void yes() { cout << "YES" << endl; }
void no() { cout << "NO" << endl; }
long long sgn(long long x) {
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
long long digitnum(long long x, long long b = 10) {
  long long ret = 0;
  for (; x; x /= b) ret++;
  return ret;
}
long long digitsum(long long x, long long b = 10) {
  long long ret = 0;
  for (; x; x /= b) ret += x % b;
  return ret;
}
string lltos(long long x) {
  string ret;
  for (; x; x /= 10) ret += x % 10 + '0';
  reverse(ret.begin(), ret.end());
  return ret;
}
long long stoll(string &s) {
  long long ret = 0;
  for (auto c : s) ret *= 10, ret += c - '0';
  return ret;
}
template <typename T>
void uniq(T &vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, deque<T> &deq) {
  for (int i = 0; i < deq.size(); i++)
    os << deq[i] << (i + 1 == deq.size() ? "" : " ");
  return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
  for (typename map<T, U>::iterator itr = map_var.begin(); itr != map_var.end();
       itr++) {
    os << "(" << itr->first << ", " << itr->second << ")";
    itr++;
    if (itr != map_var.end()) os << ",";
    itr--;
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
  for (typename set<T>::iterator itr = set_var.begin(); itr != set_var.end();
       itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, multiset<T> &set_var) {
  for (typename multiset<T>::iterator itr = set_var.begin();
       itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}
template <typename T>
void outa(T a[], long long s, long long t) {
  for (long long i = s; i <= t; i++) {
    cout << a[i];
    if (i < t) cout << " ";
  }
  cout << endl;
}
void dump_func() { cout << endl; }
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&...tail) {
  cout << head;
  if (sizeof...(Tail) > 0) cout << " ";
  dump_func(std::move(tail)...);
}
const long long L = 6;
long long hmod[L] = {950009857, 943718401, 935329793,
                     924844033, 469762049, 167772161};
struct Hash {
  long long h[L];
  Hash() {
    for (int i = 0; i < L; i++) h[i] = 0;
  }
  Hash(long long x) {
    for (int i = 0; i < L; i++) h[i] = x % hmod[i];
  }
  Hash operator+(const Hash &ope) {
    Hash h = *this;
    return h += ope;
  }
  Hash operator-(const Hash &ope) {
    Hash h = *this;
    return h -= ope;
  }
  Hash operator*(const Hash &ope) {
    Hash h = *this;
    return h *= ope;
  }
  Hash &operator+=(const Hash &ope) {
    for (int i = 0; i < L; i++) {
      h[i] += ope.h[i];
      if (h[i] >= hmod[i]) h[i] -= hmod[i];
    }
    return *this;
  }
  Hash &operator-=(const Hash &ope) {
    for (int i = 0; i < L; i++) {
      h[i] += hmod[i] - ope.h[i];
      if (h[i] >= hmod[i]) h[i] -= hmod[i];
    }
    return *this;
  }
  Hash &operator*=(const Hash &ope) {
    for (int i = 0; i < L; i++) h[i] *= ope.h[i], h[i] %= hmod[i];
    return *this;
  }
  bool operator<(const Hash &ope) const {
    for (int i = 0; i < L; i++)
      if (h[i] != ope.h[i]) return h[i] < ope.h[i];
    return false;
  }
  bool operator==(const Hash &ope) {
    for (int i = 0; i < L; i++)
      if (h[i] != ope.h[i]) return false;
    return true;
  }
  bool operator!=(const Hash &ope) { return !(*this == ope); }
};
ostream &operator<<(ostream &os, Hash &ope) {
  cout << "(";
  for (int i = 0; i < L; i++) os << ope.h[i] << (i + 1 == L ? "" : ", ");
  cout << ")";
  return os;
}
ostream &operator<<(ostream &os, const Hash &ope) {
  cout << "(";
  for (int i = 0; i < L; i++) os << ope.h[i] << (i + 1 == L ? "" : ", ");
  cout << ")";
  return os;
}
long long getrand() {
  long long ret = rand();
  ret = ret * RAND_MAX + rand();
  return ret;
}
int n;
vector<int> G[200005];
int Size[200005], depth[200005];
Hash h[200005];
int sizedfs(int v, int pre) {
  int ret = 1;
  for (int i = 0; i < G[v].size(); i++) {
    if (G[v][i] == pre) continue;
    ret += sizedfs(G[v][i], v);
  }
  return Size[v] = ret;
}
int centdfs(int v, int pre, int sz) {
  for (int i = 0; i < G[v].size(); i++) {
    if (G[v][i] == pre) continue;
    if (Size[G[v][i]] > sz / 2) return centdfs(G[v][i], v, sz);
  }
  return v;
}
void depdfs(int v, int p) {
  depth[v] = 0;
  for (auto u : G[v]) {
    if (u == p) continue;
    depdfs(u, v);
    (depth[v]) = max((depth[v]), (depth[u] + 1));
  }
}
pair<Hash, long long> calcdfs(int v, int p) {
  Hash mul = Hash(1);
  set<pair<Hash, long long> > S;
  for (auto u : G[v]) {
    if (u == p) continue;
    pair<Hash, long long> res = calcdfs(u, v);
    mul *= h[depth[v]] + res.first;
    S.insert(res);
  }
  long long sum = 0;
  for (auto x : S) sum += x.second;
  if (((long long)(G[v]).size()) <= 3) sum++;
  return pair<Hash, long long>(mul, sum);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  srand(time(NULL));
  cin >> n;
  long long u, v;
  for (long long(i) = (1); (i) <= (n - 1); (i)++) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  if (n == 1) {
    dump_func(1);
    return 0;
  }
  for (long long(i) = (0); (i) <= (n); (i)++)
    h[i] = Hash(getrand() % 900000000 + 100000000);
  sizedfs(v, -1);
  v = centdfs(v, -1, Size[v]);
  sizedfs(v, -1);
  long long w = 0;
  for (auto u : G[v]) {
    if (Size[u] * 2 == n) {
      w = u;
      break;
    }
  }
  if (w == 0) {
    depdfs(v, -1);
    dump_func(calcdfs(v, -1).second);
  } else {
    depdfs(v, w);
    pair<Hash, long long> res = calcdfs(v, w);
    depdfs(w, v);
    pair<Hash, long long> res2 = calcdfs(w, v);
    if (res.first == res2.first)
      dump_func(res.second);
    else
      dump_func(res.second + res2.second);
  }
  return 0;
}
