P15752 [JAG 2024 Summer Camp #3] Draw the Tree

给定一棵包含 $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$ 作为答案。