← 返回题目列表

Codeforces · 196/C

C. 油漆树

中文机器翻译题面 查看原题

给你一棵树,在平面上有 n 个顶点和 n 个点,没有三个点位于一条直线上。

您的任务是使用给定的点作为顶点在平面上绘制给定的树。

也就是说,您应该将树的每个顶点对应于一个点,并且每个点应该对应于一个顶点。如果树的两个顶点通过边连接,则相应的点之间应该画一条线段。与非相邻边相对应的线段不应具有公共点。与相邻边相对应的线段应该恰好有一个公共点。

输入

第一行包含一个整数 n (1 ≤ n ≤ 1500) — 树上的顶点数(以及平面上所选点的数量)。

接下来的 n - 1 行中的每一行都包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — 由第 i 条边连接的树顶点的数量。

接下来的 n 行中的每一行都包含两个以空格分隔的整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109) — 平面上第 i 个点的坐标。没有三点位于一条直线上。

保证在给定的约束下问题有解。

输出

打印 n 个不同的空格分隔整数(从 1 到 n):第 i 个数字必须等于要放置在第 i 个点处的顶点的编号(这些点按照它们在输入中列出的顺序进行编号)。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
1 3
2 3
0 0
1 1
2 0

输出 #1

1 3 2

输入 #2

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

输出 #2

4 2 1 3

注意

下面给出了示例的可能解决方案。