CF196C.Paint Tree

You are given a tree with n vertexes and n points on a plane, no three points lie on one straight line.

Your task is to paint the given tree on a plane, using the given points as vertexes.

That is, you should correspond each vertex of the tree to exactly one point and each point should correspond to a vertex. If two vertexes of the tree are connected by an edge, then the corresponding points should have a segment painted between them. The segments that correspond to non-adjacent edges, should not have common points. The segments that correspond to adjacent edges should have exactly one common point.

给你一棵包含 $n$ 个顶点的树，以及平面上的 $n$ 个点，其中任意三点不共线。

你的任务是将这棵树绘制在平面上，且必须使用给定的点作为树的顶点。

也就是说，你需要将树的每个顶点恰好对应到一个点，且每个点也必须恰好对应到一个顶点。若树中两个顶点由一条边相连，则对应的两点之间应画一条线段。对应于非相邻边的线段不应有公共点；而对应于相邻边的线段应恰好有一个公共点。

The first line contains an integer n (1 ≤ n ≤ 1500) — the number of vertexes on a tree (as well as the number of chosen points on the plane).

Each of the next n - 1 lines contains two space-separated integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — the numbers of tree vertexes connected by the i-th edge.

Each of the next n lines contain two space-separated integers x__i and y__i ( - 109 ≤ x__i, y__i ≤ 109) — the coordinates of the i-th point on the plane. No three points lie on one straight line.

It is guaranteed that under given constraints problem has a solution.

第一行包含一个整数 $n$（$1 \leq n \leq 1500$）——树的顶点数（同时也是平面上所选点的个数）。

接下来的 $n-1$ 行中，每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$）——表示第 $i$ 条边所连接的树上两个顶点的编号。

接下来的 $n$ 行中，每行包含两个用空格分隔的整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$）——表示平面上第 $i$ 个点的坐标。任意三个点均不共线。

在给定约束条件下，保证本题存在解。

Print n distinct space-separated integers from 1 to n: the i-th number must equal the number of the vertex to place at the i-th point (the points are numbered in the order, in which they are listed in the input).

If there are several solutions, print any of them.

输出 n 个互不相同的、以空格分隔的整数（取值范围为 1 到 n）：其中第 i 个数必须等于应放置在第 i 个点上的顶点编号（这些点按输入中列出的顺序进行编号）。

若存在多个解，输出任意一个即可。

The possible solutions for the sample are given below.

样例的可能解如下所示。