## ELC - Electrification

We are trying to develop the electrical power infrastructure in the small country of Byteland. For this purpose not far from each city we have built a nuclear power plant (NPP). We have also connected the nearest house to this NPP with a cable. The goal of this project is to connect all houses of each city to the source of electricity. Each house already connected to electricity become a source of electricity. Since there is a severe shortage of electrical cable, the total length of the electricity network should be kept as small as possible. In some places we can set up transformer/splitter boxes to which we can potentially connect several cables; all their endpoints are then considered connected.

### Input

*t* – the number of cities; then follows the description of each of *t* cities. [*t* <= 50]

The description of each city begins with *N* - the number of houses in the city [3 <= *N* <= 3000]. Then exactly *N* lines follow, with two real numbers: *x, y* in each, representing the coordinates of a house. [0.0 <= *x, y* <= 10000.0]

### Output

For each test case you must output a connected electrical net, e.g. all houses must be connected with each other, directly, through other houses or through transformers. For each test output integer *M* [0 <= *M* <= *N*] - the number of required transformers. On each of following *M* lines output the coordinates of the transformers *x, y* [0.0 <= *x, y* <= 10000.0]. Next output the number *K* which is equal to the number of required cables [*N+M-1 <= K <= (M+N)*(M+N-1)/2*]. On the following *K* lines output two integers *i, j* - indexes of houses or transformers. Indexes for houses begins with 0 and end with *N-1*, indexes for transformers begin with *N* and end with *N+M-1*.

### Score

The score for the problem is given as: *total_score = (200+time)*(score_1+score_2+...score_t)/200*. In the above formula, *score_i* is equal to the length of the electrical cable used for electrification of the *i*th city, and *time* is the runtime of your solution.

### Example

Input:1 4 1.0 1.0 1.0 11.0 11.0 1.0 11.0 11.0Output:1 6.0 6.0 4 0 4 1 4 2 4 4 3

**Score:**

Suppose that the solution ran for 10 seconds. The length of the cable is *score_1* = 20*sqrt(2). In this case number of points awarded to the program will be equal to 29.698485.

Added by: | Roman Sol |

Date: | 2006-04-12 |

Time limit: | 2s |

Source limit: | 60000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO |

Resource: | ZCon 2007 |