Problem: 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.

Input

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 ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — the numbers of tree vertexes connected by the i-th edge.

Each of the next n lines contain two space-separated integers xi and yi ( - 109 ≤ xi, yi ≤ 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.

Output

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.

Examples

Input

3
1 3
2 3
0 0
1 1
2 0


Output

1 3 2


Input

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


Output

4 2 1 3

Note

The possible solutions for the sample are given below.

<image> <image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
pair<long long, long long> operator+(const pair<long long, long long>& p1,
                                     const pair<long long, long long>& p2) {
  return {p1.first + p2.first, p1.second + p2.second};
}
pair<long long, long long> operator-(const pair<long long, long long>& p1,
                                     const pair<long long, long long>& p2) {
  return {p1.first - p2.first, p1.second - p2.second};
}
pair<long long, long long> operator*(const pair<long long, long long>& tp,
                                     const long long& tk) {
  return {tp.first * tk, tp.second * tk};
}
pair<long long, long long> operator/(const pair<long long, long long>& tp,
                                     const long long& tk) {
  return {tp.first / tk, tp.second / tk};
}
long long operator*(const pair<long long, long long>& p1,
                    const pair<long long, long long>& p2) {
  return p1.first * p2.first + p1.second * p2.second;
}
long long operator^(const pair<long long, long long>& p1,
                    const pair<long long, long long>& p2) {
  return p1.first * p2.second - p1.second * p2.first;
}
long long norm2(const pair<long long, long long>& tp) { return tp * tp; }
double norm(const pair<long long, long long>& tp) { return sqrt(norm2(tp)); }
pair<long long, long long> perp(const pair<long long, long long>& tp) {
  return {tp.second, -tp.first};
}
void scan(pair<long long, long long>& tp) {
  tp.first = getint();
  tp.second = getint();
}
void build() {}
int n;
vector<int> v[1515];
pair<long long, long long> p[1515];
void init() {
  n = getint();
  for (int i = 1; i < n; i++) {
    int ui = getint();
    int vi = getint();
    v[ui].push_back(vi);
    v[vi].push_back(ui);
  }
  for (int i = 0; i < n; i++) scan(p[i]);
}
int ans[1515], sz[1515];
int go(int now, int prt) {
  sz[now] = 1;
  for (int son : v[now]) {
    if (son == prt) continue;
    sz[now] += go(son, now);
  }
  return sz[now];
}
int root;
int region(const pair<long long, long long>& tp) {
  if (tp.second < 0 or (tp.second == 0 and tp.first < 0)) return 0;
  return 1;
}
bool cmp(int id1, int id2) {
  int r1 = region(p[id1] - p[root]);
  int r2 = region(p[id2] - p[root]);
  if (r1 != r2) return r1 < r2;
  return ((p[id1] - p[root]) ^ (p[id2] - p[root])) > 0;
}
bool cmp2(int id1, int id2) { return p[id1] > p[id2]; }
void go2(int now, int prt, vector<int>& cand) {
  sort(cand.begin(), cand.end(), cmp2);
  ans[cand.back()] = now;
  root = cand.back();
  cand.pop_back();
  sort(cand.begin(), cand.end(), cmp);
  size_t ptr = 0;
  for (int son : v[now]) {
    if (son == prt) continue;
    vector<int> nxt;
    for (int j = 0; j < sz[son]; j++) nxt.push_back(cand[ptr++]);
    go2(son, now, nxt);
  }
}
void solve() {
  go(1, 1);
  vector<int> cand;
  for (int i = 0; i < n; i++) cand.push_back(i);
  go2(1, 1, cand);
  for (int i = 0; i < n; i++) printf("%d%c", ans[i], " \n"[i + 1 == n]);
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}