Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Regular Forestation

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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.

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$$$.

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 < 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.

Examples

Input

13 1 5 1 7 2 4 2 8 2 11 3 12 4 7 4 12 6 11 7 13 9 10 9 12

Output

3

Input

6 1 2 1 3 2 4 3 5 3 6

Output

-1

Note

Explanation for the sample input/output #1

This is the example from the problem description.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/05/2020 23:33:35 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|