Fox And Polygon

## 题目描述 狐狸Ciel设计了一种叫“多边形”的智力游戏！它是通过把一个n变形分成三角形来进行的。目标是通过一些复杂的规则把一种分法转换成另一种分法。 n边形的一种“分法”是n - 3条不相交的对角线构成的集合。 每一步可以选择一条对角线（但不能是n边形的边）然后翻转这条对角线。 对于一条对角线AB，假设它的两边分别是三角形ABC和三角形ABD。“翻转”对角线AB，就是删除对角线AB，并添加对角线CD。 Ciel证明了对于任何一个起点和终点都有合法的翻转方式，她想让你对于任何一个n <= 1000的局面，在20000次操作内完成。 ## 输入格式 第一行是一个整数n， 表示多边形的边数 接下来n - 3行， 每一行有两个正整数a[i]，b[i],表示开始有对角线a[i]-b[i]被连接。 接下来n - 3行， 每一行两个正整数A[i], B[i]，表示目标中对角线A[i]-B[i]被连接 输入保证合法 ## 输出格式 首先输出一个整数k，表示需要k次翻转 接下来k行，每一行两个整数a[i], b[i]，表示第i次翻转对角线a[i]-b[i]， 顺序任意 如果有多重操作方法， 只需输出其中一种

Fox Ciel just designed a puzzle game called "Polygon"! It is played using triangulations of a regular $ n $ -edge polygon. The goal is to transform one triangulation to another by some tricky rules. Triangulation of an $ n $ -edge poylgon is a set of $ n-3 $ diagonals satisfying the condition that no two diagonals share a common internal point. For example, the initial state of the game may look like (a) in above figure. And your goal may look like (c). In each step you can choose a diagonal inside the polygon (but not the one of edges of the polygon) and flip this diagonal. Suppose you are going to flip a diagonal $ a–b $ . There always exist two triangles sharing $ a–b $ as a side, let's denote them as $ a–b–c $ and $ a–b–d $ . As a result of this operation, the diagonal $ a–b $ is replaced by a diagonal $ c–d $ . It can be easily proven that after flip operation resulting set of diagonals is still a triangulation of the polygon. So in order to solve above case, you may first flip diagonal $ 6–3 $ , it will be replaced by diagonal $ 2–4 $ . Then you flip diagonal $ 6–4 $ and get figure (c) as result. Ciel just proved that for any starting and destination triangulations this game has a solution. She wants you to solve it in no more than $ 20000 $ steps for any puzzle satisfying $ n<=1000 $ .

The first line contain an integer $ n $ ( $ 4<=n<=1000 $ ), number of edges of the regular polygon. Then follows two groups of $ (n-3) $ lines describing the original triangulation and goal triangulation. Description of each triangulation consists of $ (n-3) $ lines. Each line contains 2 integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ ), describing a diagonal $ a_{i}–b_{i} $ . It is guaranteed that both original and goal triangulations are correct (i. e. no two diagonals share a common internal point in both of these triangulations).

First, output an integer $ k $ ( $ 0<=k<=20,000 $ ): number of steps. Then output $ k $ lines, each containing 2 integers $ a_{i} $ and $ b_{i} $ : the endpoints of a diagonal you are going to flip at step $ i $ . You may output $ a_{i} $ and $ b_{i} $ in any order. If there are several possible solutions, output any of them.

4
1 3
2 4

1
1 3

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

2
6 3
6 4

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

3
7 3
7 2
7 1

Sample test 2 is discussed above and shown on the picture.