← 返回题目列表

Codeforces · 512/E

E. 狐狸和多边形

中文机器翻译题面 查看原题

Fox Ciel刚刚设计了一款益智游戏,名为“Polygon”!它是使用规则的 n 边多边形的三角剖分来玩的。目标是通过一些棘手的规则将一种三角测量转换为另一种三角测量。

n 边多边形的三角剖分是一组 n - 3 条对角线,满足没有两条对角线共享公共内部点的条件。

例如,游戏的初始状态可能类似于上图(a)。您的目标可能类似于 (c)。在每个步骤中,您可以选择多边形内部的一条对角线(但不是多边形的边之一)并翻转该对角线。

假设您要翻转对角线 a – b。总是存在两个共享 a – b 作为边的三角形,我们将它们表示为 a – b – c 和 a – b – d。此操作的结果是,对角线 a – b 被对角线 c – d 替换。可以很容易地证明,翻转操作后得到的对角线集仍然是多边形的三角剖分。

因此,为了解决上述情况,您可以先翻转对角线 6 – 3,它将被对角线 2 – 4 代替。然后翻转对角线 6 – 4 并得到结果图(c)。

Ciel 刚刚证明,对于任何起始和目的地三角测量,这个游戏都有一个解决方案。对于任何满足 n ≤ 1000 的谜题,她希望你用不超过 20 000 步来解决。

输入

第一行包含一个整数 n (4 ≤ n ≤ 1000),正多边形的边数。

然后是两组 (n - 3) 条线,描述原始三角测量和目标三角测量。

每个三角剖分的描述由 (n - 3) 行组成。每行包含 2 个整数 ai 和 bi (1 ≤ ai, bi ≤ n),描述一条对角线 ai – bi。

保证原始三角剖分和目标三角剖分都是正确的(即,在这两个三角剖分中没有两条对角线共享公共内部点)。

输出

首先输出一个整数k (0 ≤ k ≤ 20, 000):步数。

然后输出 k 行,每行包含 2 个整数 ai 和 bi:你要在步骤 i 翻转的对角线的端点。您可以按任意顺序输出 ai 和 bi。

如果有多种可能的解决方案,则输出其中任何一个。

示例

输入 #1

4
1 3
2 4

输出 #1

1
1 3

输入 #2

6
2 6
3 6
4 6
6 2
5 2
4 2

输出 #2

2
6 3
6 4

输入 #3

8
7 1
2 7
7 3
6 3
4 6
6 1
6 2
6 3
6 4
6 8

输出 #3

3
7 3
7 2
7 1

注意

示例测试 2 已在上面讨论并显示在图片中。