Problem Description

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.

Input Format

The first line contains an integer $n$.

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

Output Format

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.

5
1 3
1 4

-1

8
6 8
5 8
2 4
2 5
1 5

3 2
2 4
7 8
6 8
2 1
1 5
8 1

Hint

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