Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3862
Intersection

Time Limit: 3 Seconds      Memory Limit: 131072 KB      Special Judge

Edward has 2n points on the plane conveniently labeled with 1,2,…,2n. Each point is connected exactly with another point by a segment.

Edward finds that some segments intersecting with some others. So he wants to eliminate those intersections with the following operation: choose two points i and j (1 ≤ i, j ≤ 2n) and swap their coordinates.

For example, Edward has 4 points (0, 0), (0, 1), (1, 1), (1, 0). Point 1 is connected with point 3 and point 2 is connected with 4. Edward can choose to swap the coordinates of point 2 and point 3.

Edward wants to know whether it is possible to use at most n + 10 operations to achieve his goal.

No two points coincide and no three points are on the same line.

#### Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer n (1 ≤ n ≤ 100000).

Each of the following 2n lines contains 2 integers xi, yi which denotes the point (xi, yi). (|xi|, |yi| ≤ 109).

Each of the following n lines contains 2 integers ai, bi (1 ≤ ai, bi ≤ 2n, aibi), which means point ai and point bi are connected by a segment.

The sum of values n for all the test cases does not exceed 300000.

#### Output

For each test case, print a line containing an integer m, indicating the number of operations needed. You must assure that m is no larger than n + 10. If you cannot find such a solution, just output "-1" and ignore the following output.

In the next m lines, each contains two integers i and j (1 ≤ i, j ≤ 2n), indicating an operation, separated by one space.

If there are multiple solutions, any of them is accepted.

#### Sample Input

1
2
0 0
0 1
1 1
1 0
1 3
2 4


#### Sample Output

1
2 3


Author: LIN, Xi
Source: The 15th Zhejiang University Programming Contest
Submit    Status