题目描述

译自 CERC 2018「E. Trees Gump」

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

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

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

输入格式

第一行包含一个整数 $N$，表示树顶数和军队数。树顶和军队都用 $0\ldots N-1$ 编号；

接下来 $N-1$ 行，每行两个整数，表示这两支军队应在同一条索道两端；

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

输出格式

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

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

样例 1

input

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

output

0 3
3 1
1 4
4 2

样例 2

input

3
1 2
0 2
0 0
1 1
2 3

output

0 1
1 2

数据范围与提示

$1\le N\le 10^3,0\le X_i,Y_i\le 10^9$