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 = ;

const int M = ;

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) > ;

    }

}p[N];

void dfs1(ll u,ll fa){

    sz[u]=;

    for(int i=;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+,p+e+);

    ans[p[s].id]=u;

    int cnt=;

    for(int i=;i<edg[u].size();i++){

        ll v=edg[u][i];

        if(v==fa)continue;

        dfs2(v,u,s++cnt,s++cnt+sz[v]-);

        cnt+=sz[v];

    }

}

int main() {

    ll T,u,v;

    scanf("%lld",&n);

    for(int i=;i<n;i++){

        scanf("%lld%lld",&u,&v);

        edg[u].pb(v);edg[v].pb(u);

    }

    for(int i=;i<n;i++){

        scanf("%lld%lld",&p[i].x,&p[i].y);

        p[i].id=i;

    }

    dfs1(,);

    dfs2(,,,n-);

    for(int i=;i<n;i++)printf("%lld ",ans[i]);printf("\n");

    return ;

}