Odd Degree Spanning Tree in a Triangulation Graph

Given a convex polygon with n vertices labeled in clockwise order from 1 to n, and n-3 distinct diagonals of the polygon (which do not intersect except at their endpoints), we obtain an undirected graph with n vertices and 2n-3 edges. Note that a diagonal of a convex polygon is a line segment connecting two distinct vertices that are not adjacent on the polygon.

This graph is exactly the triangulation graph of the convex polygon. Your task is to select a subset of n-1 edges (i.e. construct a spanning tree of the graph using only the given edges) so that every vertex has an odd degree. If no such spanning tree exists, output -1.

Note: In any tree, the sum of all vertex degrees is 2(n-1). Therefore a necessary condition for a spanning tree with all vertices of odd degree is that n is even.

inputFormat

The input consists of:

1. The first line contains a single integer n (3 ≤ n ≤ 10^5), the number of vertices of the polygon.
2. Each of the next n-3 lines contains two integers u and v (1 ≤ u, v ≤ n, and u and v are not adjacent on the polygon) representing a diagonal of the polygon. All diagonals are distinct and any two diagonals can intersect only at endpoints.

It is guaranteed that the given diagonals, together with the boundary edges of the polygon, form a triangulation of the convex polygon.

outputFormat

If a valid spanning tree exists, output n-1 lines, each containing two integers representing an edge in the tree. The edges must be chosen from the polygon's boundary edges or the provided diagonals.

If no valid spanning tree exists, output a single line containing -1.

sample

3

-1