Problem Description

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.

Input Format

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 Format

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

3
1 2
2 3
10 10
10 20
20 10

1 2 3

5
1 2
1 3
1 4
4 5
10 10
10 30
30 10
30 30
20 25

5 4 2 3 1

6
1 2
2 3
1 4
4 5
4 6
10 60
10 40
40 50
40 30
70 30
70 10

6 5 4 1 2 3

Hint

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$.

Translated by ChatGPT 5