{"raw_statement":[{"iden":"statement","content":"给定平面上的 $N$ 个点，和一棵大小为 $N$ 的树 $T$，保证这棵树上每个点的度数至多为 $3$，树上节点按 $1\\sim N$ 编号。\n\n你需要为平面上的点使用 $1\\sim N$ 的编号重编号之后，对于所有树上的边 $e=(u,v)$，将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。\n\n试构造一组方案，保证一定有解。"},{"iden":"input","content":"第一行一个整数 $N$。\n\n接下来 $N-1$ 行，一行两个整数 $a,b$，表示有一条从 $a$ 连向 $b$ 的边。\n\n接下来 $N$ 行，一行两个整数 $x,y$，表示一个点的横纵坐标为 $(x,y)$。保证这 $N$ 个点两两不同，且没有任意三点共线。"},{"iden":"output","content":"输出一行 $N$ 个整数，第 $i$ 个数应为原本的第 $i$ 个点的标号。"},{"iden":"note","content":"### 样例 3 解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1sz6z9sk.png)\n\n蓝色数字表示所分配的编号，黑色数字表示原本的编号。\n\n### 数据规模与约定\n\n对于所有数据，保证 $0\\le x,y\\le 10^9$。\n\n| Subtask 编号 |                 特殊限制                  | 分数 |\n| :----------: | :--------------------------------------: | :--: |\n|     $1$      | $3\\le N\\le 2\\times 10^5$，所有点均在凸包上 | $10$ |\n|     $2$      |             $1\\le N\\le 4000$             | $15$ |\n|     $3$      |             $1\\le N\\le 10^4$             | $15$ |\n|     $4$      |         $1\\le N\\le 8\\times 10^4$         | $35$ |\n|     $5$      |         $1\\le N\\le 2\\times 10^5$         | $25$ |"}],"translated_statement":null,"sample_group":[["3\n1 2\n2 3\n10 10\n10 20\n20 10","1 2 3"],["5\n1 2\n1 3\n1 4\n4 5\n10 10\n10 30\n30 10\n30 30\n20 25","5 4 2 3 1"],["6\n1 2\n2 3\n1 4\n4 5\n4 6\n10 60\n10 40\n40 50\n40 30\n70 30\n70 10","6 5 4 1 2 3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}