Trees Gump#9751
The tall trees in the Jumbarian jungle are of great strategic importance. The Jumbarian army headquarters has selected trees located relatively close to one another and decided to build a tree house on each of them, with each house occupied by a single army unit.
Movement of personnel and supplies between the treetops will be supported by a system of bidirectional zip lines connecting pairs of tree houses. For safety reasons, no two zip lines may intersect (when viewed from above).
A total of army units have already been selected, and a list of pairs of units has been prepared. Units in each pair are intended to be stationed at the opposite ends of a single zip line. The list contains exactly n - 1 pairs. It is guaranteed that this list ensures connectivity of the entire area; that is, once the units are assigned to trees, every unit will be able to reach any other unit using only the zip lines specified in the list.
The only remaining task is to install the zip lines between the tree houses in such a way that the deployment of units satisfies the above requirements.
The first line contains one integer n~(1 \le n \le 1000), the number of treetops and army units. Both the treetops and the army units are labeled 0, 1, \dots, n - 1.
The next n - 1 lines describe the list of unit pairs. Each line contains two integers — the labels of two units that are to be placed at the opposite ends of a single zip line.
The following lines contain the coordinates of the selected treetops. The (i + 1)-th of these lines contains two integers x_i and y_i~(0 \le x_i, y_i \le 10^9), the coordinates of the treetop labeled . It is guaranteed that no three treetops are collinear.
Print a list of all pairs of treetops that must be connected by zip lines. The list should consist of n - 1 lines, each containing two distinct tree labels.
If multiple valid solutions exist, print any one of them.
Example 1
Example 2