#1658. 「CERC2018」Trees Gump

「CERC2018」Trees Gump

题目描述

译自 CERC 2018E. Trees Gump

在 Jumbarian 雨林中,大树的战略地位十分重要。Jumbarian 军队的首领选择了互相距离较近的 NN 棵树,并决定这 NN 棵树上每棵都要建一个树屋,并安排一支军队。人和材料在树与树之间的运输要依靠双向连接的索道。出于安全因素考虑,从卫星上看任意两条索道之间都没有交叉。

现在已经选出了 NN 支军队,并且已经列出了两支军队为一对的清单。在同一对的两支军队应当在同一条索道的两端操控这条索道。军队对数比军队数少一,这就表明这一区域的连通性是有保证的。即,在分配军队后,每一支军队都可以只经过列表中出现的索道到达任意地方。

剩余的工作就是如何在树顶安装索道,才能使得可以按上面的规则安排军队。

输入格式

第一行包含一个整数 NN,表示树顶数和军队数。树顶和军队都用 0N10\ldots N-1 编号;

接下来 N1N-1 行,每行两个整数,表示这两支军队应在同一条索道两端;

接下来 NN 行给出每个树顶的坐标,第 i+1i+1 行包含两个数 Xi,YiX_i,Y_i,表示第 ii 棵树的坐标。任意三棵树不会在同一条直线上。

输出格式

输出 N1N-1 行,表示安装索道的方案,每行输出两个数 x,yx,y,表示 x,yx,y 两棵树之间建一条索道。

如果有多组解满足题目要求,可以输出任意一组。

样例 1

5
0 1
1 2
2 3
3 4
0 0
9 9
2 3
3 2
7 8
0 3
3 1
1 4
4 2
3
1 2
0 2
0 0
1 1
2 3
0 1
1 2

数据范围与提示

1N103,0Xi,Yi1091\le N\le 10^3,0\le X_i,Y_i\le 10^9