Fox And Polygon

2000ms

262144K

Description:

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.

$\text{[math]}$

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 20 000 steps for any puzzle satisfying n ≤ 1000.

Input:

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).

Output:

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.

Sample Input:

4
1 3
2 4

Sample Output:

1
1 3

Sample Input:

Sample Output:

2
6 3
6 4

Sample Input:

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF512E