P7460 [CERC2018] Trees Gump

**译自[ [CERC2018]](https://contest.felk.cvut.cz/18cerc/) [Trees Gump](https://contest.felk.cvut.cz/18cerc/solved/gump.pdf)** 在 Jumbarian 雨林中，大树的战略地位十分重要。Jumbarian 军队的首领选择了互相距离较近的 $N$ 棵树，并决定这 $N$ 棵树上每棵都要建一个树屋，并安排一支军队。人和材料在树与树之间的运输要依靠双向连接的索道。出于安全因素考虑，从卫星上看任意两条索道之间都没有交叉。 现在已经选出了 $N$ 支军队，并且已经列出了两支军队为一对的清单。在同一对的两支军队应当在同一条索道的两端操控这条索道。军队对数比军队数少一，这就表明这一区域的连通性是有保证的。即，在分配军队后，每一支军队都可以只经过列表中出现的索道到达任意地方。 剩余的工作就是如何在树顶安装索道，才能使得可以按上面的规则安排军队。

第一行包含一个整数 $N$，表示树顶数和军队数。树顶和军队都用 $0…N-1$ 编号； 接下来 $N-1$ 行，每行两个整数，表示这两支军队应在同一条索道两端； 接下来 $N$ 行给出每个树顶的坐标，第 $i+1$ 行包含两个数 $X_i,Y_i$，表示第 $i$ 棵树的坐标。任意三棵树不会在同一条直线上。

输出 $N-1$ 行，表示安装索道的方案，每行输出两个数 $x,y$，表示 $x,y$ 两棵树之间建一条索道。 如果有多组解满足题目要求，可以输出任意一组。

$1≤N≤10^3,0≤X_i,Y_i≤10^9$