题目描述

通常所说的“造林”是种植大量树木，使其成长为森林，往往用于替代被砍伐的森林。

有趣的是，图论研究者对“制造森林”有另一种理解：从一棵树中删除一个点。

一棵树是由 $N$ 个节点和 $N-1$ 条边组成的连通图。

设 $u$ 是树 $U$ 中度数至少为 $2$ 的节点。删除节点 $u$ 以及所有与它相连的边后，原树会分裂成两个或更多互不连通的较小树，这些树共同组成一片森林。

现在定义树的同构。

设 $V(S)$ 和 $V(T)$ 分别为树 $S$ 和树 $T$ 的节点集合。如果存在一个双射

$$f:V(S)\to V(T),$$

使得对任意 $s_i,s_j\in V(S)$：

$$s_i,s_j$$

在 $S$ 中有边相连，当且仅当

$$f(s_i),f(s_j)$$

在 $T$ 中有边相连，则称树 $S$ 和树 $T$ 相同，即二者同构。

若删除树 $U$ 中的节点 $u$ 后：

1. 得到至少两棵互不连通的树；
2. 所有这些树两两同构；

则称节点 $u$ 为一个良好切割点。

给定一棵树 $U$，请判断是否存在良好切割点。

如果存在，请输出删除一个良好切割点后，能够得到的连通树数量的最大值。

示例说明

下图是一棵有 $13$ 个节点的树。

节点 $4$ 是唯一的良好切割点。删除节点 $4$ 后，得到三棵同构的链状树：

$$\{5,1,7,13\},$$ $$\{8,2,11,6\},$$ $$\{3,12,9,10\}.$$

图中的三部分分别标记为 $A,B,C$。

输入格式

第一行包含一个整数 $N$：

$$3\le N\le 4000,$$

表示树的节点数。

接下来 $N-1$ 行，每行包含两个整数 $a_i,b_i$：

$$1\le a_i<b_i\le N,$$

表示节点 $a_i$ 与 $b_i$ 之间有一条边。

保证给定图是一棵树。

输出格式

如果存在良好切割点，输出删除一个良好切割点后能够得到的连通树数量的最大值。

如果不存在良好切割点，输出：

-1

样例 1

输入

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

输出

3

样例 2

输入

6
1 2
1 3
2 4
3 5
3 6

输出

-1