Problem Description

Given $N$ points on a plane and a tree $T$ of size $N$, where each node in the tree has a degree of at most 3, and the nodes are numbered from 1 to $N$.

You need to reassign the numbers from 1 to $N$ to the points on the plane such that for every edge $e = (u, v)$ in the tree, the points $u$ and $v$ on the plane are connected by a line segment. These line segments must not intersect except at their endpoints.

Construct a solution that ensures a valid arrangement.

Input Format

The first line contains an integer $N$.

The next $N-1$ lines each contain two integers $a$ and $b$, indicating an edge from $a$ to $b$.

The following $N$ lines each contain two integers $x$ and $y$, representing the coordinates $(x, y)$ of a point. It is guaranteed that these $N$ points are distinct and no three points are collinear.

Output Format

Output one line containing $N$ integers, where the $i$-th integer is the original label of the $i$-th point.

Sample Input and Output

Sample Input #1

3
1 2
2 3
10 10
10 20
20 10

Sample Output #1

1 2 3

Sample Input #2

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

Sample Output #2

5 4 2 3 1

Sample Input #3

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

Sample Output #3

6 5 4 1 2 3

Notes

Sample 3 Explanation

The blue numbers represent the assigned labels, and the black numbers represent the original labels.

Data Constraints

For all data, $0 \le x, y \le 10^9$.

见题面 Input 部分

见题面 Output 部分