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.

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 (?-?10⁹?≤?x_i,?y_i?≤?10⁹) — 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.

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.

3
1 3
2 3
0 0
1 1
2 0

1 3 2

4
1 2
2 3
1 4
-1 -2
3 5
-3 3
2 0

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2005;
const int M = 24005;
pair<ll,ll>ori;
vector<ll>edg[N];
ll n,m,k;
ll sz[N],ans[N];
struct man{
    ll x,y,id;
    bool operator < (const man & b) const {
        return (x-ori.first)*(b.y-ori.second) - (y-ori.second)*(b.x-ori.first) > 0;
    }
}p[N];
void dfs1(ll u,ll fa){
    sz[u]=1;
    for(int i=0;i<edg[u].size();i++){
        ll v=edg[u][i];
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
void dfs2(ll u,ll fa,ll s,ll e){
    int pos;
    ll x,y;
    x=y=1e10;
    for(int i=s;i<=e;i++){
        if(p[i].x<x||((p[i].x==x)&&p[i].y<y)){
            x=p[i].x;y=p[i].y;pos=i;
        }
    }
    ori.first=x;ori.second=y;
    swap(p[s],p[pos]);
    sort(p+s+1,p+e+1);
    ans[p[s].id]=u;
    int cnt=0;
    for(int i=0;i<edg[u].size();i++){
        ll v=edg[u][i];
        if(v==fa)continue;
        dfs2(v,u,s+1+cnt,s+1+cnt+sz[v]-1);
        cnt+=sz[v];
    }
}
int main() {
    ll T,u,v;
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&u,&v);
        edg[u].pb(v);edg[v].pb(u);
    }
    for(int i=0;i<n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
        p[i].id=i;
    }
    dfs1(1,0);
    dfs2(1,0,0,n-1);
    for(int i=0;i<n;i++)printf("%lld ",ans[i]);printf("\n");
    return 0;
}