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

You are given a tree of $N$ vertices, numbered $1, 2, \ldots, N$. You want to determine a positive integer value $M$ and draw this tree on a region $\mathbf{R} = \{(x, y) \mid 0 \leq x \leq M - 1, 0 \leq y \leq 1\}$ on a two-dimensional coordinate plane. In this drawing, the vertices of the tree should be placed at grid points within $\mathbf{R}$, and the edges of the tree should be drawn as straight line segments. Furthermore, these line segments representing different edges of the tree should not share any points other than their endpoints. More formally, you want to construct a mapping $\mathbf{p}$ from the vertex set of tree $\mathbf{T}$ to the set of grid points $\{(x, y) \mid x \in \{0, 1, \ldots, M - 1\}, y \in \{0, 1\}\}$ such that the following properties are satisfied: - For any distinct vertices $v_i$ and $v_j$ in $\mathbf{T}$, $\mathbf{p}(v_i)$ and $\mathbf{p}(v_j)$ are distinct. - For any distinct edges $e_i = (u_i, v_i)$ and $e_j = (u_j, v_j)$ in $\mathbf{T}$, the line segments $\mathbf{seg}_i$ connecting $\mathbf{p}(u_i)$ and $\mathbf{p}(v_i)$, and $\mathbf{seg}_j$ connecting $\mathbf{p}(u_j)$ and $\mathbf{p}(v_j)$ do not share any points inside $\mathbf{seg}_i$ (excluding the endpoints) or inside $\mathbf{seg}_j$ (excluding the endpoints). Your task is to determine if such a drawing is possible by choosing an appropriate $M$, and if possible, find the minimum value of $M$.

The input consists of a single test case of the following format. $$\begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \end{aligned}$$ The first line consists of an integer $N$, which is between $1$ and $50,000$, inclusive. Each of the following $N - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq N$). $u_i$ and $v_i$ denote the endpoints of the $i$-th edge of $\mathbf{T}$. It is guaranteed that the given graph is a tree.

Output a single integer — the minimum possible value of $M$ to achieve the goal. If it is impossible to do so, output $-1$ as the answer.