Page not loading? Try clicking here.
Placeholder

#10410
Grading on hold

Fence Design 60s 1024MB

Problems

You are hired as a temporary employee of the Fence Construction Company and have been tasked with finishing the design of the fencing for a field. Each fence must run in a straight line between two poles. Each pole occupies a single point and the location of each pole is fixed. No three poles are collinear. Fences cannot intersect each other, except possibly at their endpoints (the poles).

The design was started by someone else, but they quit the project after adding exactly two fences. You need to finish their design. To impress your bosses and clients, you want the design to have as many fences as possible, regardless of their lengths.

Given the positions of the poles and the already-built fences, please find a way to add as many fences as possible such that no pair of fences (new or existing) intersect each other, except possibly at their endpoints (the poles).


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. Each test case starts with a single line containing an integer \mathbf{N}, indicating the number of poles. Then, \mathbf{N} lines follow. The i-th of these lines contains two integers \mathbf{X_i} and \mathbf{Y_i}, representing the X and Y coordinates of the i-th pole's position. The last two lines for each test case represent the two existing fences. These two lines contain two integers each: \mathbf{P_k} and \mathbf{Q_k}, representing that the k-th existing fence runs between the \mathbf{P_k}-th and the \mathbf{Q_k}-th pole (poles are numbered starting from 1).


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of fences that can be added to the design (not including the existing ones). Then, output y more lines. Each line must contain two distinct integers i and j (both between 1 and \mathbf{N}, inclusive), representing a different fence that connects the i-th and j-th poles. No pair of the y+2 fences (the existing fences as well as the ones you have added) may overlap, except possibly at their endpoints.


Example 

2
4
0 0
0 1
1 1
1 0
1 2
3 4
5
0 0
0 1
1 1
1 0
2 3
1 2
3 5
Case #1: 3
1 4
2 3
4 2
Case #2: 6
5 4
2 4
5 2
1 4
4 3
3 2
The following pictures show the poles and fences in the given samples. The fences with the wider blue line on them are the existing ones, and the rest show the way of adding a maximum number of fences shown in the sample output.

Source

GCJ 2021r3 C

You must sign in to write code.