说明

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1, 2, \ldots, N$。你需要确定一个正整数 $M$，并将这棵树绘制在二维坐标平面上的一个区域 $\mathbf{R} = \{(x, y) \mid 0 \leq x \leq M - 1, 0 \leq y \leq 1\}$ 内。

在此绘制中，树的顶点应放置在 $\mathbf{R}$ 内的网格点上，树的边应绘制为直线段。此外，代表树的不同边的这些直线段，除了它们的端点外，不应共享任何点。

更正式地说，你需要构造一个从树 $\mathbf{T}$ 的顶点集到网格点集 $\{(x, y) \mid x \in \{0, 1, \ldots, M - 1\}, y \in \{0, 1\}\}$ 的映射 $\mathbf{p}$，使得满足以下性质：

• 对于 $\mathbf{T}$ 中任意两个不同的顶点 $v_i$ 和 $v_j$，$\mathbf{p}(v_i)$ 和 $\mathbf{p}(v_j)$ 是不同的。
• 对于 $\mathbf{T}$ 中任意两条不同的边 $e_i = (u_i, v_i)$ 和 $e_j = (u_j, v_j)$，连接 $\mathbf{p}(u_i)$ 和 $\mathbf{p}(v_i)$ 的线段 $\mathbf{seg}_i$，与连接 $\mathbf{p}(u_j)$ 和 $\mathbf{p}(v_j)$ 的线段 $\mathbf{seg}_j$，在 $\mathbf{seg}_i$ 内部（不包括端点）和 $\mathbf{seg}_j$ 内部（不包括端点）不共享任何点。

你的任务是判断是否可以通过选择一个合适的 $M$ 来实现这样的绘制。如果可能，请找出 $M$ 的最小值。

输入格式

输入包含一个单独的测试用例，格式如下。

$$\begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \end{aligned}$$

第一行包含一个整数 $N$，其值在 $1$ 到 $50,000$ 之间（含端点）。

接下来的 $N - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq N$）。$u_i$ 和 $v_i$ 表示 $\mathbf{T}$ 的第 $i$ 条边的两个端点。

保证给定的图是一棵树。

输出格式

输出一个整数——为实现目标所需的最小可能的 $M$ 值。如果不可能实现，则输出 $-1$ 作为答案。

6
1 2
1 3
1 4
1 5
1 6

3

21
1 2
1 3
1 4
1 5
6 7
6 8
6 9
6 10
11 12
11 13
11 14
11 15
16 17
16 18
16 19
16 20
5 21
10 21
15 21
20 21

-1

18
1 2
2 3
2 4
2 5
1 6
6 7
6 8
6 9
1 12
10 11
11 12
12 13
13 14
1 16
15 16
16 17
17 18

11

21
20 10
7 2
7 17
18 5
3 1
15 17
11 7
14 18
11 21
6 2
8 19
17 14
4 18
16 17
9 10
19 17
18 12
15 3
13 15
16 10

11