Cable Car Installation

In the Jumbarian rainforest the trees occupy a strategic position. The leader of the Jumbarian army has selected N trees that are near each other, and on top of each tree a treehouse will be built and an army will be stationed. Transportation of people and materials between the trees is achieved by installing bidirectional cable cars (ropes) between pairs of trees. For safety reasons the cables, when viewed from a satellite, must not cross; that is, any two cables (represented as straight segments) should not intersect in their interiors.

There are exactly N armies available and a list of N-1 unordered pairs of armies has been prepared. In each listed pair the two armies will control the two ends of a cable. Since a tree‐network with N-1 pairs is connected, every army can reach any other using only the cables in the list.

The remaining work is to decide how to install the cables on the treetops. In other words, you are given a set of N trees (with fixed coordinates) that lie in convex position and a tree (an undirected connected acyclic graph) with nodes labeled 1 to N (each node representing an army). You must assign each army to a distinct tree such that when drawing, for every edge connecting armies u and v, the straight-line segment joining the trees assigned to u and v does not cross any other such segment. Formally, if the trees' positions are given in the plane as points and the assignment gives a permutation f on {1,…,N}, then for every cable there is a chord between two points and any two chords (except those sharing an endpoint) must not intersect. It can be shown that a sufficient condition to guarantee non‐crossing is to choose a permutation in which the cyclic order of trees (when sorted by polar angle) corresponds to a DFS order of the tree. (All formulas are given in LaTeX format, for example, the number of armies is \(N\) and the number of cables is \(N-1\).)

Your task is to find any valid assignment. It is guaranteed that the given trees are in convex position and the given list of pairs forms a tree.

inputFormat

The input begins with a line containing an integer \(N\) (\(1 \le N \le 10^5\)).

This is followed by \(N\) lines, each containing two integers \(x\) and \(y\) representing the coordinates of a tree. The trees are given in an arbitrary order but are guaranteed to lie in convex position.

Then follow \(N-1\) lines, each containing two integers \(u\) and \(v\) (\(1 \le u, v \le N\)) denoting that the armies labeled \(u\) and \(v\) must share one cable.

outputFormat

Output a permutation of \(N\) integers. The \(i\)th number represents the index of the tree (as given in the input order) to which the army that appears in the \(i\)th position in the chosen DFS order is assigned. This assignment must guarantee that for every cable (edge) connecting two armies, the straight-line segment between the assigned trees does not cross any other such segment.

If there are multiple valid answers, output any one.

sample

3
0 0
1 0
0 1
1 2
2 3

1 2 3