Jumbarian 森林中的巨树在战略上非常重要。Jumbarian 陆军总部挑选了 $N$ 棵彼此相当接近的树，并决定在每棵树上建造一个树屋，每个树屋将由一个陆军小队驻守。树顶之间的人员和物资流动将通过连接两两树顶的双向滑索系统来支持。出于安全原因，从卫星上观察时，任意两条滑索都不能相交。

已经选定了 $N$ 个小队，并创建了这些小队之间的配对列表。配对中的两个小队预计将在同一条滑索的两端工作。列表中的配对数量比小队数量少一个。事实证明，该列表确保了区域的连通性，即在小队部署到树木上之后，每个小队都能够仅通过列表中的滑索到达任何其他小队。

要使该方案付诸实施，剩下要做的就是以一种允许按照上述规则部署小队的方式在树顶之间安装滑索。

输入格式

第一行包含一个整数 $N$，表示树顶和陆军小队的数量（$1 \le N \le 1000$）。树顶和陆军小队都用 $0, 1, \dots, N-1$ 编号。

接下来的 $N-1$ 行包含小队配对列表。每行包含两个小队的编号，表示它们预计在同一条滑索的两端工作。

接下来的 $N$ 行给出所选树顶的坐标。其中的第 $i+1$ 行包含两个整数 $X_i$ 和 $Y_i$（$0 \le X_i, Y_i \le 10^9$），表示编号为 $i$ 的树顶的坐标。

保证没有三棵树顶在同一条直线上。

输出格式

输出需要用滑索连接的所有树对的列表。该列表包含 $N-1$ 行，每行包含两个不同树木的编号。

如果该问题有多个解，输出其中任意一个。

样例

输入样例 1

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

输出样例 1

0 3
3 1
1 4
4 2

输入样例 2

3
1 2
0 2
0 0
1 1
2 3

输出样例 2

0 1
1 2