P8999 [CEOI 2022] Drawing

You are given $N$ points on the plane and a tree $T$ with $N$ vertices. It is guaranteed that the degree of every vertex in the tree is at most $3$, and the vertices of the tree are numbered from $1$ to $N$. You need to relabel the given planar points using the labels $1 \sim N$. After relabeling, for every tree edge $e=(u,v)$, connect planar point $u$ and planar point $v$ with a line segment. The requirement is that any two such segments have no intersection points other than possibly at their endpoints. Construct and output one valid assignment. It is guaranteed that a solution always exists.

The first line contains an integer $N$. The next $N-1$ lines each contain two integers $a, b$, meaning there is an edge connecting $a$ and $b$. The next $N$ lines each contain two integers $x, y$, meaning there is a point with coordinates $(x, y)$. It is guaranteed that all $N$ points are pairwise distinct, and no three points are collinear.

Output one line with $N$ integers. The $i$-th number should be the assigned label of the original $i$-th point.

### Explanation of Sample 3  The blue numbers show the assigned labels, and the black numbers show the original labels. ### Constraints For all testdata, it is guaranteed that $0 \le x, y \le 10^9$. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $3 \le N \le 2\times 10^5$, all points are on the convex hull | $10$ | | $2$ | $1 \le N \le 4000$ | $15$ | | $3$ | $1 \le N \le 10^4$ | $15$ | | $4$ | $1 \le N \le 8\times 10^4$ | $35$ | | $5$ | $1 \le N \le 2\times 10^5$ | $25$ | Translated by ChatGPT 5