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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    int n;
    BidirectionalGraph graph;
    long[] hashs;
    long[][] childHashs;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      graph = new BidirectionalGraph(n, n - 1);
      graph.init(n);
      for (int i = 1; i < n; ++i) {
        graph.add(in.nextInt() - 1, in.nextInt() - 1);
      }
      hashs = new long[n << 1];
      Arrays.fill(hashs, -1);
      childHashs = new long[n << 1][3];
      long[] res = new long[n];
      int m = 0, idx = (n << 1) - 1;
      for (int i = 0; i < n; ++i)
        if (graph.outDegree[i] < 4) {
          hashs[idx] = -1;
          res[m++] = calcHash(-1, i, idx);
        }
      Arrays.sort(res, 0, m);
      out.println(LongArrayUtils.unique(res, 0, m));
    }

    long calcHash(int u, int v, int idx) {
      if (hashs[idx] >= 0) {
        return hashs[idx];
      }
      int m = 0;
      for (int edgeIdx = graph.lastOut[v]; edgeIdx >= 0; edgeIdx = graph.nextOut[edgeIdx]) {
        int w = graph.toIdx[edgeIdx];
        if (w != u) {
          childHashs[idx][m++] = calcHash(v, w, edgeIdx);
        }
      }
      Arrays.sort(childHashs[idx], 0, m);
      hashs[idx] = HashUtils.calc(childHashs[idx], 0, m);
      return hashs[idx];
    }

  }

  static class DirectedGraph {
    public int vertexCnt;
    public int edgeCnt;
    public int[] fromIdx;
    public int[] toIdx;
    public int[] nextIn;
    public int[] nextOut;
    public int[] lastIn;
    public int[] lastOut;
    public int[] inDegree;
    public int[] outDegree;

    public DirectedGraph(int vertexCapacity, int edgeCapacity) {
      this.fromIdx = new int[edgeCapacity];
      this.toIdx = new int[edgeCapacity];
      this.lastIn = new int[vertexCapacity];
      this.lastOut = new int[vertexCapacity];
      this.nextIn = new int[edgeCapacity];
      this.nextOut = new int[edgeCapacity];
      this.inDegree = new int[vertexCapacity];
      this.outDegree = new int[vertexCapacity];
    }

    public void init(int vertexCnt) {
      this.vertexCnt = vertexCnt;
      this.edgeCnt = 0;
      Arrays.fill(inDegree, 0, vertexCnt, 0);
      Arrays.fill(outDegree, 0, vertexCnt, 0);
      Arrays.fill(lastIn, 0, vertexCnt, -1);
      Arrays.fill(lastOut, 0, vertexCnt, -1);
    }

    public void add(int fromIdx, int toIdx) {
      this.fromIdx[edgeCnt] = fromIdx;
      this.toIdx[edgeCnt] = toIdx;
      ++outDegree[fromIdx];
      ++inDegree[toIdx];
      nextOut[edgeCnt] = lastOut[fromIdx];
      lastOut[fromIdx] = edgeCnt;
      nextIn[edgeCnt] = lastIn[toIdx];
      lastIn[toIdx] = edgeCnt;
      ++edgeCnt;
    }

  }

  static class LongArrayUtils {
    public static int unique(long[] values, int fromIdx, int toIdx) {
      if (fromIdx == toIdx) return 0;
      int res = 1;
      for (int i = fromIdx + 1; i < toIdx; ++i) {
        if (values[i - 1] != values[i]) {
          values[fromIdx + res++] = values[i];
        }
      }
      return res;
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

    public void close() {
      writer.close();
    }

  }

  static class BidirectionalGraph extends DirectedGraph {
    public BidirectionalGraph(int vertexCapacity, int edgeCapacity) {
      super(vertexCapacity, edgeCapacity << 1);
    }


    public void add(int u, int v) {
      super.add(u, v);
      super.add(v, u);
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' '
          || c == '\n'
          || c == '\r'
          || c == '\t'
          || c < 0;
    }

  }

  static class HashUtils {
    public static long START_SEED = 100000000000000003L;
    public static long END_SEED = 1000000000000000003L;
    public static int BASE = 1000000007;

    public static long calc(long[] values, int fromIdx, int toIdx) {
      long res = START_SEED;
      for (int i = fromIdx; i < toIdx; ++i) {
        res = (res * BASE) ^ values[i];
      }
      return res * END_SEED;
    }

  }
}

