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.PrintWriter;
import java.util.Arrays;
import java.util.Set;
import java.util.InputMismatchException;
import java.util.Random;
import java.io.IOException;
import java.util.HashSet;
import java.util.Comparator;
import java.io.InputStream;

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

    static class TaskD {
        int[] degree;
        long[] hash1;
        long[] hash2;
        int[] size;
        Graph graph;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.readInt();
            int[] u = new int[n - 1];
            int[] v = new int[n - 1];
            IOUtils.readIntArrays(in, u, v);
            MiscUtils.decreaseByOne(u, v);
            graph = BidirectionalGraph.createGraph(n, u, v);
            hash1 = new long[2 * n - 2];
            hash2 = new long[2 * n - 2];
            Arrays.fill(hash1, -1);
            Arrays.fill(hash2, -1);
            size = new int[2 * n - 2];
        /*RootHash[] rootHashes = new RootHash[2 * (n - 1)];
        for (int i = 0; i < rootHashes.length; ++i) {
            rootHashes[i] = null;
        }*/
            degree = new int[n];
            for (int i = 0; i < n; ++i) {
                degree[i] = graph.degree(i);
            }
            Set<LongLongPair> hashes = new HashSet<LongLongPair>();
            long[] pow1 = IntegerUtil.generatePowers(HashUtil.MULTIPLIER, 2 * n + 1, HashUtil.FIRST_MOD);
            long[] pow2 = IntegerUtil.generatePowers(HashUtil.MULTIPLIER, 2 * n + 1, HashUtil.SECOND_MOD);
            for (int i = 0; i < n; ++i) {
                if (degree[i] == 4) continue;
                long h1 = calculateHash(i, -1, HashUtil.FIRST_MOD, pow1, hash1).hash;
                long h2 = calculateHash(i, -1, HashUtil.SECOND_MOD, pow2, hash2).hash;
                hashes.add(new LongLongPair(h1, h2));
            }
            out.println(hashes.size());
        }

        private TaskD.RootHash calculateHash(int node, int parent, long mod, long[] pow, long[] hash) {
            int length = parent == -1 ? degree[node] : degree[node] - 1;
            long[] sHash = new long[length];
            long[] sSize = new long[length];
            int child = 0;
            for (int i = graph.firstOutbound(node); i != -1; i = graph.nextOutbound(i)) {
                int cNode = graph.destination(i);
                if (cNode == parent) continue;
                if (hash[i] == -1) {
                    TaskD.RootHash rh = calculateHash(cNode, node, mod, pow, hash);
                    hash[i] = rh.hash;
                    size[i] = rh.size;
                }
                sHash[child] = hash[i];
                sSize[child] = size[i];
                child++;
            }
            int[] order = ArrayUtils.order(sHash);
            long res = 0;
            int sz = 1;
            for (int i : order) {
                res += (sHash[i] * pow[sz]) % mod;
                sz += sSize[i];
            }
            res = (res + pow[sz]) % mod;
            sz++;
            TaskD.RootHash rh = new TaskD.RootHash();
            rh.size = sz;
            rh.hash = res;
            return rh;
        }

        static class RootHash {
            public int size = -1;
            public long hash = -1;

        }

    }

    static class ArrayUtils {
        public static int[] order(final long[] array) {
            Integer[] order = new Integer[array.length];
            double d = 0;
            for (int i = 0; i < order.length; ++i) {
                order[i] = i;
            }
            Arrays.sort(order, new Comparator<Integer>() {
                public int compare(Integer a, Integer b) {
                    return Long.signum(array[a] - array[b]);
                }
            });
            int[] order_ret = new int[order.length];
            for (int i = 0; i < order.length; ++i) {
                order_ret[i] = order[i];
            }
            return order_ret;
        }

    }

    static class IntegerUtil {
        public static long[] generatePowers(long base, int count, long mod) {
            long[] result = new long[count];
            if (count != 0) {
                result[0] = 1 % mod;
            }
            for (int i = 1; i < count; i++) {
                result[i] = result[i - 1] * base % mod;
            }
            return result;
        }

    }

    static class LongLongPair implements Comparable<LongLongPair> {
        public final long first;
        public final long second;

        public LongLongPair(long first, long second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            LongLongPair pair = (LongLongPair) o;

            return first == pair.first && second == pair.second;
        }

        @SuppressWarnings("Since15")
        public int hashCode() {
            int result = Long.hashCode(first);
            result = 31 * result + Long.hashCode(second);
            return result;
        }

        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({"unchecked", "Since15"})
        public int compareTo(LongLongPair o) {
            int value = Long.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            return Long.compare(second, o.second);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            // InputMismatchException -> UnknownError
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            } else if (c == '+') {
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class MiscUtils {
        public static void decreaseByOne(int[]... arrays) {
            for (int[] array : arrays) {
                for (int i = 0; i < array.length; ++i) {
                    array[i]--;
                }
            }
        }

    }

    static interface Edge {
    }

    static class HashUtil {
        public static final long MULTIPLIER;
        public static final long FIRST_MOD;
        public static final long SECOND_MOD;

        static {
            Random random = new Random(System.currentTimeMillis());
            FIRST_MOD = Prime.nextPrime((long) (1e9 + random.nextInt((int) 1e9)));
            SECOND_MOD = Prime.nextPrime((long) (1e9 + random.nextInt((int) 1e9)));
            MULTIPLIER = random.nextInt((int) 1e9 - 257) + 257;
        }
    }

    static class Prime {
        public static boolean isPrime(long number) {
            if (number < 2) {
                return false;
            }
            for (long i = 2; i * i <= number; i++) {
                if (number % i == 0) {
                    return false;
                }
            }
            return true;
        }

        public static long nextPrime(long from) {
            if (from <= 2) {
                return 2;
            }
            from += 1 - (from & 1);
            while (!isPrime(from)) {
                from += 2;
            }
            return from;
        }

    }

    static class BidirectionalGraph extends Graph {
        public int[] transposedEdge;

        public BidirectionalGraph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public BidirectionalGraph(int vertexCount, int edgeCapacity) {
            super(vertexCount, 2 * edgeCapacity);
            transposedEdge = new int[2 * edgeCapacity];
        }

        public static BidirectionalGraph createGraph(int vertexCount, int[] from, int[] to) {
            BidirectionalGraph graph = new BidirectionalGraph(vertexCount, from.length);
            for (int i = 0; i < from.length; i++) {
                graph.addSimpleEdge(from[i], to[i]);
            }
            return graph;
        }


        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            int lastEdgeCount = edgeCount;
            super.addEdge(fromID, toID, weight, capacity, reverseEdge);
            super.addEdge(toID, fromID, weight, capacity, reverseEdge == -1 ? -1 : reverseEdge + 1);
            this.transposedEdge[lastEdgeCount] = lastEdgeCount + 1;
            this.transposedEdge[lastEdgeCount + 1] = lastEdgeCount;
            return lastEdgeCount;
        }


        protected int entriesPerEdge() {
            return 2;
        }


        protected void ensureEdgeCapacity(int size) {
            if (size > edgeCapacity()) {
                super.ensureEdgeCapacity(size);
                transposedEdge = resize(transposedEdge, edgeCapacity());
            }
        }

    }

    static class IOUtils {
        public static void readIntArrays(InputReader in, int[]... arrays) {
            for (int i = 0; i < arrays[0].length; ++i) {
                for (int j = 0; j < arrays.length; ++j) {
                    arrays[j][i] = in.readInt();
                }
            }
        }

    }

    static class Graph {
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        private long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;
        private boolean[] isRemoved;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int maxEdge) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[maxEdge];
            to = new int[maxEdge];
            nextOutbound = new int[maxEdge];
            flags = new int[maxEdge];
            isRemoved = new boolean[maxEdge];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1) {
                nextOutbound[edgeCount] = firstOutbound[fromID];
            } else {
                nextOutbound[edgeCount] = -1;
            }
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1) {
                    nextInbound[edgeCount] = firstInbound[toID];
                } else {
                    nextInbound[edgeCount] = -1;
                }
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null) {
                    this.capacity = new long[from.length];
                }
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null) {
                    this.weight = new long[from.length];
                }
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null) {
                edges[edgeCount] = createEdge(edgeCount);
            }
            return edgeCount++;
        }

        protected final GraphEdge createEdge(int id) {
            return new GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        protected final int edgeCapacity() {
            return from.length;
        }

        public final int firstOutbound(int vertex) {
            int id = firstOutbound[vertex];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int nextOutbound(int id) {
            id = nextOutbound[id];
            while (id != -1 && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int degree(int vertex) {
            int degree = 0;
            for (int j = firstOutbound(vertex); j != -1; j = nextOutbound(j)) {
                degree++;
            }
            return degree;
        }

        public final int destination(int id) {
            return to[id];
        }

        public final boolean isRemoved(int id) {
            return isRemoved[id];
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null) {
                    edges = resize(edges, newSize);
                }
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null) {
                    nextInbound = resize(nextInbound, newSize);
                }
                if (weight != null) {
                    weight = resize(weight, newSize);
                }
                if (capacity != null) {
                    capacity = resize(capacity, newSize);
                }
                if (reverseEdge != null) {
                    reverseEdge = resize(reverseEdge, newSize);
                }
                flags = resize(flags, newSize);
                isRemoved = resize(isRemoved, newSize);
            }
        }

        protected final boolean[] resize(boolean[] array, int size) {
            boolean[] newArray = new boolean[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }
}

