A forestation is an act of planting a bunch of trees to grow a forest, usually to replace a forest that had been cut down. Strangely enough, graph theorists have another idea on how to make a forest, i.e. by cutting down a tree!

A tree is a graph of $$$N$$$ nodes connected by $$$N - 1$$$ edges. Let $$$u$$$ be a node in a tree $$$U$$$ which degree is at least $$$2$$$ (i.e. directly connected to at least $$$2$$$ other nodes in $$$U$$$). If we remove $$$u$$$ from $$$U$$$, then we will get two or more disconnected (smaller) trees, or also known as forest by graph theorists. In this problem, we are going to investigate a special forestation of a tree done by graph theorists.

Let $$$V(S)$$$ be the set of nodes in a tree $$$S$$$ and $$$V(T)$$$ be the set of nodes in a tree $$$T$$$. Tree $$$S$$$ and tree $$$T$$$ are identical if there exists a bijection $$$f : V(S) \rightarrow V(T)$$$ such that for all pairs of nodes $$$(s_i, s_j)$$$ in $$$V(S)$$$, $$$s_i$$$ and $$$s_j$$$ is connected by an edge in $$$S$$$ if and only if node $$$f(s_i)$$$ and $$$f(s_j)$$$ is connected by an edge in $$$T$$$. Note that $$$f(s) = t$$$ implies node $$$s$$$ in $$$S$$$ corresponds to node $$$t$$$ in $$$T$$$.

We call a node $$$u$$$ in a tree $$$U$$$ as a good cutting point if and only if the removal of $$$u$$$ from $$$U$$$ causes two or more disconnected trees, and all those disconnected trees are pairwise identical.

Given a tree $$$U$$$, your task is to determine whether there exists a good cutting point in $$$U$$$. If there is such a node, then you should output the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point.

For example, consider the following tree of $$$13$$$ nodes.

$\text{[math]}$

There is exactly one good cutting point in this tree, i.e. node $$$4$$$. Observe that by removing node $$$4$$$, we will get three identical trees (in this case, line graphs), i.e. $$$\{5, 1, 7, 13\}$$$, $$$\{8, 2, 11, 6\}$$$, and $$$\{3, 12, 9, 10\}$$$, which are denoted by $$$A$$$, $$$B$$$, and $$$C$$$ respectively in the figure.

The bijection function between $$$A$$$ and $$$B$$$: $$$f(5) = 8$$$, $$$f(1) = 2$$$, $$$f(7) = 11$$$, and $$$f(13) = 6$$$.
The bijection function between $$$A$$$ and $$$C$$$: $$$f(5) = 3$$$, $$$f(1) = 12$$$, $$$f(7) = 9$$$, and $$$f(13) = 10$$$.
The bijection function between $$$B$$$ and $$$C$$$: $$$f(8) = 3$$$, $$$f(2) = 12$$$, $$$f(11) = 9$$$, and $$$f(6) = 10$$$.

Of course, there exists other bijection functions for those trees.

Input

Input begins with a line containting an integer: $$$N$$$ ($$$3 \le N \le 4000$$$) representing the number of nodes in the given tree. The next $$$N - 1$$$ lines each contains two integers: $$$a_i$$$ $$$b_i$$$ ($$$1 \le a_i \lt b_i \le N$$$) representing an edge $$$(a_i,b_i)$$$ in the given tree. It is guaranteed that any two nodes in the given tree are connected to each other by a sequence of edges.

Output

Output in a line an integer representing the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point, or output -1 if there is no such good cutting point.

Note

Explanation for the sample input/output #1

This is the example from the problem description.

Regular Forestation

Examples