Non‐Crossing Tree Embedding

Given a set of (N) points in the plane and a tree (T) on (N) vertices (with vertices numbered from (1) to (N) and each vertex having degree at most (3)), reassign the labels of the points (using labels (1,\dots,N)) so that if for every edge (e=(u,v)) in (T) the corresponding points (with their new labels) are connected by a straight line segment, then any two segments intersect only at common endpoints. It can be shown that a solution always exists.

One standard approach is to choose a bijection between the vertices of (T) and the given points in such a way that the points (when arranged according to their new labels) form a convex polygon. Then, any tree drawn on a convex set of points is drawn without crossing segments. One way to obtain this is to sort the points by their polar angle about the centroid (which gives a convex ordering) and to order the tree vertices using a DFS traversal from vertex (1) (breaking ties by the natural order of the vertex labels). Finally, map the (i)th vertex in the DFS order to the (i)th point in the sorted (convex) order. This yields a permutation (\pi) of ({1,2,\dots,N}) as the new labels.

Note: The input points are given in general position so that the polar sort yields a simple polygon.

inputFormat

The input begins with an integer (N) (the number of points and vertices).

Then follow (N) lines, each containing two real numbers representing the coordinates of a point in the plane.

After that, there are (N-1) lines; each line contains two integers (u) and (v) denoting an edge of the tree (T). It is guaranteed that (T) is connected and that every vertex has degree at most 3.

outputFormat

Print a permutation of (N) integers separated by spaces. For each vertex (i) ((1 \le i \le N)), output its new label. The new labels correspond to the assignment of points (ordered in convex (polar) order) to the vertices as determined by a DFS traversal on (T). With this assignment, when for every edge (e=(u,v)) the line segment connecting the points with labels corresponding to (u) and (v) is drawn, any two segments intersect only at their endpoints.

sample

3
0 0
1 0
0 1
1 2
1 3

2 3 1