Moving Bricks

Brickgao used to be a real tall, wealthy, handsome man and you might know him well. If you don't, please draw attention to the details below.
Brickgao tried his fortune in investment of golden bricks with his two partners LS and Jne. Because he knew little about investment he gave his total trust and bank savings to his two partners who looked smart.
However, due to the bad luck and lack of business skills, LS and Jne used up Brickgao's fund, and nothing in return. Their investment failed and the three become diaosi.
Brickgao had no other choice but to earn a living as a construction worker and he found his place on a building site moving bricks which of course was not golden ones. There were many brick fragment scattered on the site and workers had to move them to the building that under construction. Brickgao was made to cope with the task.
The problem is that the Brickgao couldn’t carry more than two bricks at a time since they were too heavy. Also, if he had taken a brick, he couldn’t put it anywhere except the goal building — his inherent sense of order does not let him do so.
You are given N pairs of coordinates of the bricks and the coordinates of the goal building. It is known that the Brickgao covers the distance between any two points in the time equal to the squared length of the segment between the points. It is also known that initially the coordinates of the Brickgao and the goal building are the same. You are asked to find such an order of bricks, that the Brickgao could move all the bricks to the building in a minimum time period. You can assume the no two bricks shared the same coordinates. If more than one optimum moving sequence Brickgao could find, he would choose the smallest lexicographic one because of the inherent sense of order.

The first line of the input file contains an integer T which indicates the number of test cases. The first line of each case contains the building's coordinates x ,y. The second line contains number N (1<= N < 20) — the amount of bricks on the building site. The following N lines contain the bricks' coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

For each test case, first you should print "Case x:" in a line, where x stands for the case number started with 1. Then two lines follow: the first line output the only number — the minimum time Brickgao needed to move the bricks to building, and the second line output the optimum order for Brickgao to move the bricks. Each brick in the input is described by its index number (from 1 to N).

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

Case 1:
8
1 2
Case 2:
32
1 2 3

In the first test, Brickgao gets brick 1 and brick 2 and returns to the building.
In the second test, Brickgao first moves brick 1 and brick 2 to the building and then gets the third and returns to the building.

WHU

2012 Multi-University Training Contest 9