#include <bits/stdc++.h>
using namespace std;
class PT {
 public:
  int x, y, i;
  bool operator<(const PT& p) const {
    if (x == p.x) {
      return y < p.y;
    }
    return x < p.x;
  }
  long long disTo(const PT& p) const {
    long long dx = (long long)x - (long long)p.x;
    long long dy = (long long)y - (long long)p.y;
    return dx * dx + dy * dy;
  }
};
vector<int> eg[1600];
int u[1600];
int pre[1600];
int c[1600];
PT pt[1600];
int mt[1600];
int tm[1600];
int stk[1600];
int dfs(int x) {
  int i, y;
  c[x] = 1;
  for (i = 0; i < eg[x].size(); i++) {
    y = eg[x][i];
    if (!u[y]) {
      u[y] = 1;
      c[x] += dfs(y);
      pre[y] = x;
    }
  }
  return c[x];
}
bool cmp(const PT& a, const PT& b) {
  return (long long)a.x * (long long)b.y > (long long)a.y * (long long)b.x;
}
inline int tri(PT& a, PT& b, PT& c) {
  long long d =
      ((long long)a.x * (long long)b.y + (long long)b.x * (long long)c.y +
       (long long)c.x * (long long)a.y) -
      ((long long)a.y * (long long)b.x + (long long)b.y * (long long)c.x +
       (long long)c.y * (long long)a.x);
  return d > 0 ? 1 : -1;
}
void create(int o, int L, int R, int pr) {
  int i, z, top;
  if (R - L == 1) {
    mt[o] = L;
    return;
  } else if (R - L == 2) {
    mt[o] = L;
    for (i = 0; i < eg[o].size(); i++) {
      if (eg[o][i] != pre[o]) {
        mt[eg[o][i]] = L + 1;
        return;
      }
    }
  }
  PT p;
  sort(pt + L, pt + R);
  if (pr == -1) {
    z = L;
  } else {
    p = pt[mt[pr]];
    if (tri(pt[L], pt[R - 1], p) > 0) {
      top = 0;
      stk[0] = R - 1;
      for (i = R - 2; i >= L; i--) {
        while (top > 0 && tri(pt[stk[top - 1]], pt[stk[top]], pt[i]) < 0) top--;
        stk[++top] = i;
      }
      for (i = 0; i < top; i++) {
        if (tri(pt[stk[i]], pt[stk[i + 1]], p) < 0) {
          z = stk[i];
          break;
        }
      }
    } else {
      top = 0;
      stk[0] = L;
      for (i = L + 1; i < R; i++) {
        while (top > 0 && tri(pt[stk[top - 1]], pt[stk[top]], pt[i]) < 0) top--;
        stk[++top] = i;
      }
      for (i = 0; i < top; i++) {
        if (tri(pt[stk[i]], pt[stk[i + 1]], p) < 0) {
          z = stk[i];
          break;
        }
      }
    }
    swap(pt[z], pt[L]);
    z = L;
  }
  mt[o] = z;
  L++;
  for (i = L; i < R; i++) {
    pt[i].x -= pt[z].x;
    pt[i].y -= pt[z].y;
  }
  sort(pt + L, pt + R, cmp);
  for (i = L; i < R; i++) {
    pt[i].x += pt[z].x;
    pt[i].y += pt[z].y;
  }
  for (i = 0; i < eg[o].size(); i++) {
    if (eg[o][i] == pre[o]) continue;
    create(eg[o][i], L, L + c[eg[o][i]], o);
    L += c[eg[o][i]];
  }
}
int main() {
  int n, i, j, x, y;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d %d", &x, &y);
    x--;
    y--;
    eg[x].push_back(y);
    eg[y].push_back(x);
    u[i] = 0;
  }
  for (i = 0; i < n; i++) {
    scanf("%d %d", &x, &y);
    pt[i].x = x;
    pt[i].y = y;
    pt[i].i = i;
  }
  u[0] = 1;
  pre[0] = -1;
  dfs(0);
  create(0, 0, n, -1);
  for (i = 0; i < n; i++) {
    tm[pt[mt[i]].i] = i + 1;
  }
  for (i = 0; i < n - 1; i++) {
    printf("%d ", tm[i]);
  }
  printf("%d\n", tm[n - 1]);
  return 0;
}

### Prompt

In CPP, your task is to solve the following 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>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class PT {
 public:
  int x, y, i;
  bool operator<(const PT& p) const {
    if (x == p.x) {
      return y < p.y;
    }
    return x < p.x;
  }
  long long disTo(const PT& p) const {
    long long dx = (long long)x - (long long)p.x;
    long long dy = (long long)y - (long long)p.y;
    return dx * dx + dy * dy;
  }
};
vector<int> eg[1600];
int u[1600];
int pre[1600];
int c[1600];
PT pt[1600];
int mt[1600];
int tm[1600];
int stk[1600];
int dfs(int x) {
  int i, y;
  c[x] = 1;
  for (i = 0; i < eg[x].size(); i++) {
    y = eg[x][i];
    if (!u[y]) {
      u[y] = 1;
      c[x] += dfs(y);
      pre[y] = x;
    }
  }
  return c[x];
}
bool cmp(const PT& a, const PT& b) {
  return (long long)a.x * (long long)b.y > (long long)a.y * (long long)b.x;
}
inline int tri(PT& a, PT& b, PT& c) {
  long long d =
      ((long long)a.x * (long long)b.y + (long long)b.x * (long long)c.y +
       (long long)c.x * (long long)a.y) -
      ((long long)a.y * (long long)b.x + (long long)b.y * (long long)c.x +
       (long long)c.y * (long long)a.x);
  return d > 0 ? 1 : -1;
}
void create(int o, int L, int R, int pr) {
  int i, z, top;
  if (R - L == 1) {
    mt[o] = L;
    return;
  } else if (R - L == 2) {
    mt[o] = L;
    for (i = 0; i < eg[o].size(); i++) {
      if (eg[o][i] != pre[o]) {
        mt[eg[o][i]] = L + 1;
        return;
      }
    }
  }
  PT p;
  sort(pt + L, pt + R);
  if (pr == -1) {
    z = L;
  } else {
    p = pt[mt[pr]];
    if (tri(pt[L], pt[R - 1], p) > 0) {
      top = 0;
      stk[0] = R - 1;
      for (i = R - 2; i >= L; i--) {
        while (top > 0 && tri(pt[stk[top - 1]], pt[stk[top]], pt[i]) < 0) top--;
        stk[++top] = i;
      }
      for (i = 0; i < top; i++) {
        if (tri(pt[stk[i]], pt[stk[i + 1]], p) < 0) {
          z = stk[i];
          break;
        }
      }
    } else {
      top = 0;
      stk[0] = L;
      for (i = L + 1; i < R; i++) {
        while (top > 0 && tri(pt[stk[top - 1]], pt[stk[top]], pt[i]) < 0) top--;
        stk[++top] = i;
      }
      for (i = 0; i < top; i++) {
        if (tri(pt[stk[i]], pt[stk[i + 1]], p) < 0) {
          z = stk[i];
          break;
        }
      }
    }
    swap(pt[z], pt[L]);
    z = L;
  }
  mt[o] = z;
  L++;
  for (i = L; i < R; i++) {
    pt[i].x -= pt[z].x;
    pt[i].y -= pt[z].y;
  }
  sort(pt + L, pt + R, cmp);
  for (i = L; i < R; i++) {
    pt[i].x += pt[z].x;
    pt[i].y += pt[z].y;
  }
  for (i = 0; i < eg[o].size(); i++) {
    if (eg[o][i] == pre[o]) continue;
    create(eg[o][i], L, L + c[eg[o][i]], o);
    L += c[eg[o][i]];
  }
}
int main() {
  int n, i, j, x, y;
  scanf("%d", &n);
  for (i = 1; i < n; i++) {
    scanf("%d %d", &x, &y);
    x--;
    y--;
    eg[x].push_back(y);
    eg[y].push_back(x);
    u[i] = 0;
  }
  for (i = 0; i < n; i++) {
    scanf("%d %d", &x, &y);
    pt[i].x = x;
    pt[i].y = y;
    pt[i].i = i;
  }
  u[0] = 1;
  pre[0] = -1;
  dfs(0);
  create(0, 0, n, -1);
  for (i = 0; i < n; i++) {
    tm[pt[mt[i]].i] = i + 1;
  }
  for (i = 0; i < n - 1; i++) {
    printf("%d ", tm[i]);
  }
  printf("%d\n", tm[n - 1]);
  return 0;
}

```