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 已在上面讨论并显示在图片中。