Description

Translated from [CERC2018] Trees Gump.

In the Jumbarian rainforest, tall trees have great strategic value. The leader of the Jumbarian army chose $N$ trees that are close to each other, and decided to build a treehouse on each of the $N$ trees and station one army unit there. Transporting people and materials between trees relies on bidirectional cableways. For safety reasons, when viewed from a satellite, no two cableways cross each other.

Now $N$ army units have been selected, and a list of pairs of army units has been made. The two army units in the same pair should operate the same cableway from its two ends. The number of pairs is one less than the number of army units, which means connectivity in this area is guaranteed. That is, after assigning the army units, each army unit can reach any place using only the cableways that appear in the list.

The remaining task is how to install the cableways between the tree tops so that the army units can be assigned according to the rules above.

Input Format

The first line contains an integer $N$, the number of tree tops and the number of army units. Both tree tops and army units are numbered $0 \ldots N-1$.

The next $N-1$ lines each contain two integers, meaning that these two army units should be at the two ends of the same cableway.

The next $N$ lines give the coordinates of each tree top. Line $i+1$ contains two numbers $X_i, Y_i$, the coordinates of the $i$-th tree. No three trees lie on the same straight line.

Output Format

Output $N-1$ lines describing an installation plan for the cableways. Each line outputs two numbers $x, y$, meaning that a cableway is built between trees $x$ and $y$.

If there are multiple solutions that satisfy the requirements, output any one of them.

5
0 1
1 2
2 3
3 4
0 0
9 9
2 3
3 2
7 8

0 3
3 1
1 4
4 2

3
1 2
0 2
0 0
1 1
2 3

0 1
1 2

Hint

$1 \le N \le 10^3$, $0 \le X_i, Y_i \le 10^9$.

Translated by ChatGPT 5