Connecting Treeland

The government of Treeland is planning to build a new road network. There are \(2N\) cities in Treeland and \(N\) roads have already been built. Each of the \(N\) existing roads is a straight-line segment connecting two cities, and no two roads intersect even at their endpoints.

Your task is to add exactly \(N-1\) new roads so that:

1. Each new road is a straight-line segment connecting two cities.
2. Any two roads can only meet at a common endpoint.
3. The entire network is connected, i.e. any city can reach any other city through a sequence of roads.

Note: It is guaranteed that the \(N\) existing roads have no intersections at all (including at endpoints), which implies that they connect \(2N\) distinct cities in \(N\) disjoint pairs. You must choose your new roads so that, in combination with the existing ones, the resulting set of \(2N-1\) roads is non-crossing and connects all cities.

Hint: It is given that all the \(2N\) cities lie in a convex position. Therefore, if you sort the cities in counterclockwise order based on their polar angle around the center of all cities, the boundary of the convex hull forms a cycle. By connecting some consecutive pairs along this cycle (avoiding those already connected by an existing road) and selecting only the necessary edges to connect all components, you may obtain a valid solution.

inputFormat

The input is given as follows:

N
x1 y1
x2 y2
... (2N lines for the coordinates of the cities)
u1 v1
u2 v2
... (N lines, each containing two integers u and v representing an already built road between cities u and v, cities are numbered from 1 to 2N)

You may assume that all cities are in a convex position and that the existing roads are non-intersecting (even at endpoints).

outputFormat

Output exactly \(N-1\) lines. Each line should contain two integers representing the endpoints of one new road that you add. The new roads must ensure that the entire network becomes connected and remain non-crossing (roads may only intersect at common endpoints).

sample

2
0 0
1 0
1 1
0 1
1 3

1 2