P8921 "MdOI R5" Triangulation

There is a regular $n$-gon whose vertices are labeled $1$ to $n$ in clockwise order. You are given $n - 3$ **distinct** diagonals of this polygon, and they satisfy that **they can only intersect at vertices**. In this way, we obtain an undirected graph with $n$ vertices and $2n - 3$ edges. A diagonal of a convex polygon is a line segment connecting two vertices that are **different** and **not adjacent on the polygon**. In fact, this undirected graph can be any triangulation graph of a convex $n$-gon. You need to construct a spanning tree of this undirected graph such that the degree of every vertex is **odd**, or report that there is no solution.

The first line contains an integer $n$. The next $n - 3$ lines each contain two integers $u, v$, representing a given diagonal $(u, v)$.

If there is no solution, output one line with the integer $-1$. If there is a solution, output $n - 1$ lines, each containing two integers $u, v$, representing an edge $(u, v)$ in the spanning tree you constructed.

For $100\%$ of the testdata, $3 \le n \le 3 \times 10^5$. $\operatorname{Subtask} 1(9\%)$: $n \le 10$. $\operatorname{Subtask} 2(1\%)$: $n$ is odd. $\operatorname{Subtask} 3(10\%)$: $u = 1$. $\operatorname{Subtask} 4(30\%)$: $n \le 100$. $\operatorname{Subtask} 5(30\%)$: $n \le 5 \times 10^3$. $\operatorname{Subtask} 6(20\%)$: no special constraints. Translated by ChatGPT 5