给你一棵树,在平面上有 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
注意
下面给出了示例的可能解决方案。