“植树造林”通常指种植树木以形成森林，通常是为了替代被砍伐的森林。奇怪的是，图论学家对于如何“造林”有另一种想法，即通过砍伐一棵树来实现！

树是一个由 $N$ 个节点和 $N-1$ 条边组成的图。设 $u$ 是树 $U$ 中的一个节点，其度数至少为 2（即在 $U$ 中直接与至少 2 个其他节点相连）。如果我们从 $U$ 中移除 $u$，我们将得到两个或多个不连通的（较小的）树，图论学家也称之为森林。在本题中，我们将研究图论学家对树进行的一种特殊“造林”方式。

设 $V(S)$ 为树 $S$ 的节点集合，$V(T)$ 为树 $T$ 的节点集合。如果存在一个双射 $f : V(S) \to V(T)$，使得对于 $V(S)$ 中的所有节点对 $(s_i, s_j)$，$s_i$ 和 $s_j$ 在 $S$ 中有边相连当且仅当节点 $f(s_i)$ 和 $f(s_j)$ 在 $T$ 中有边相连，则称树 $S$ 和树 $T$ 是全等的。注意，$f(s) = t$ 意味着 $S$ 中的节点 $s$ 对应于 $T$ 中的节点 $t$。

如果移除树 $U$ 中的节点 $u$ 会导致产生两个或多个不连通的树，且所有这些不连通的树两两全等，则称节点 $u$ 为一个“好的切割点”。

给定一棵树 $U$，你的任务是确定 $U$ 中是否存在好的切割点。如果存在这样的节点，你应该输出通过移除该好的切割点所能获得的不连通树的最大数量。

例如，考虑以下包含 13 个节点的树。

在这棵树中恰好存在一个好的切割点，即节点 4。观察可知，通过移除节点 4，我们将得到三棵全等的树（在本例中为线图），即 $\{5, 1, 7, 13\}$、$\{8, 2, 11, 6\}$ 和 $\{3, 12, 9, 10\}$，在图中分别记为 $A, B$ 和 $C$。

• $A$ 和 $B$ 之间的双射函数：$f(5) = 8, f(1) = 2, f(7) = 11, f(13) = 6$。
• $A$ 和 $C$ 之间的双射函数：$f(5) = 3, f(1) = 12, f(7) = 9, f(13) = 10$。
• $B$ 和 $C$ 之间的双射函数：$f(8) = 3, f(2) = 12, f(11) = 9, f(6) = 10$。

当然，这些树之间还存在其他双射函数。

输入格式

输入的第一行包含一个整数 $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

样例输出 1

3

说明 1

这是题目描述中的示例。

样例输入 2

6
1 2
1 3
2 4
3 5
3 6

样例输出 2

-1