Paint & Wine 是萨格勒布第一家提供绘画课程的画室，课程中还会提供一杯葡萄酒。在课程中，学生会得到一个特定的主题，在专业画家的指导下，通常都能画出令人印象深刻的作品。

Ante 是一位专业画家，Luka 是他的学生，这个任务讲述了一节比平时多喝了一点酒的绘画课的故事。

Ante：“给我画一棵树！” Luka：“好的。你想要什么样的树？棕榈树、橡树、松树……？” Ante：“我想要一个连通的无环无向图！” Luka：“这没问题……还有其他要求吗？” Ante：“我希望没有节点的度数超过 3！” Luka：“嗯，好的……好吧，这样的树有很多。” Ante：“这是边列表，我就要这一棵！” Luka：“好的，哇。不过，画它的方法有很多种。” Ante：“这是平面上我希望节点被放置的位置列表。我也不希望看到任何相交的边。” Luka：“交给我吧！”

你的任务是帮助 Luka 根据 Ante 的意愿画出这棵树。更准确地说，给定一棵树的描述（其中没有节点的度数超过 3）以及平面上的一组点，找到一个节点到点的双射，使得当树的边被画成连接对应点的线段时，它们不会相交（端点除外）。

输入格式

输入的第一行包含一个整数 $N$，表示树的节点数，同时也表示平面上的点数。

接下来的 $N - 1$ 行描述树的边，每行一条。每条边由两个整数 $a$ 和 $b$ 描述，表示被边连接的节点标签。节点标签为从 $1$ 到 $N$ 的整数。

保证每个节点的度数最多为 3。

接下来的 $N$ 行包含画树时要使用的点，每行一个。每个点由一对整数坐标描述。没有两个点具有相同的坐标，且没有三个点共线。

输出格式

输出一行，包含 $1$ 到 $N$ 的一个排列。第 $i$ 个数字应该是映射到第 $i$ 个输入点的节点标签。

如果有多个有效的解决方案，输出其中任意一个。保证解一定存在。

子任务

在所有子任务中，点的坐标均为 $0$ 到 $10^9$ 之间的整数。

样例

输入 1

3
1 2
2 3
10 10
10 20
20 10

输出 1

1 2 3

输入 2

5
1 2
1 3
1 4
4 5
10 10
10 30
30 10
30 30
20 25

输出 2

5 4 2 3 1

输入 3

6
1 2
2 3
1 4
4 5
4 6
10 60
10 40
40 50
40 30
70 30
70 10

输出 3

6 5 4 1 2 3

说明

第三个样例的示意图：

蓝色数字代表节点标签，黑色数字代表点索引。