Programming League 2004/05

Many of Johnny's school friends have perfected the art of folding a square sheet of paper into beautiful shapes (known as origami). Johnny attempted to follow suit, but to his dismay he found that his fingers were a little to clumsy for the task in hand. After spending yet another day creating something especially disastrous (later named "From the series: Crumpled Pieces of Paper Seen with an Artist's Eye, No. 27"), Johnny decided he'd had enough. Therefore he proudly proclaimed to all his friends that origami was not fit for serious people, and that he intended to become the master of kirigami, the art of cutting paper. But after experimenting with kirigami for a few weeks, he sold the rather miserable results of his labour to the local confetti store, and announced that true beauty lay in convex polygons, and that they were the only shapes a true artist should ever cut. Still, if a person is as lazy and inapt as Johnny, even such a seemingly simple task may turn out a real challenge.

The method Johnny uses to create works of art consists of several steps. First, he takes a sheet of paper in the shape of a convex polygon and uses a ruler and pencil to draw a convex polygon (lying entirely within the sheet). Then, he proceeds to cut it out using a ruler and a razor-edged paper cutter. Every cut is thus a segment of a line, reaching from one edge of the sheet of paper to another, and adjacent to one side of the drawn polygon. Johnny then discards the cut off corner of the sheet and continues cutting until the shape outlined in pencil is completely cut out. Since he is extremely disinclined to perform hard work, please write a program to help him minimise the total length of the lines along which the paper is cut.

Input

Input begins with a single integer t (t=200). t test cases follow.

Each test case starts with a line containing two integers m n, denoting the number of vertices of the sheet of paper and the shape drawn on it, respectively (3<=m,n<=600). The next m lines contain two integers ai bi each (-20000<=ai, bi <=20000), corresponding to the x and y coordinates of vertices of the sheet of paper (given in clockwise order). The description of the shape drawn on the sheet follows, given in the next n lines in a similar form.

Output

For the i-th test case output a line with the text case i Y or case i N, specifying whether you wish to solve the given case. In the former case, in the next line output a permutation of the numbers 1...n denoting the order in which Johnny is supposed to cut out the respective sides of the shape drawn on the sheet (vertices are numbered from 1 to n in the input order, and side s connects vertices s and 1 + s mod n).

Score

The score awarded to your program is the sum of scores taken over all test cases you chose to solve.

For each test case, the score awarded to your program is equal to the ratio of the perimeter of the sheet of paper and the total length of the lines along which the paper is cut.

Example

Input:
3
4 4
0 0
0 2
2 2
2 0
0 1
1 2
2 1
1 0
4 3
0 0
0 3
3 3
3 0
1 1
1 2
2 2
4 3
0 0
0 3
3 3
3 0
1 1
1 2
2 2

Output:
case 1 Y
1 2 3 4
case 2 Y
1 2 3
case 3 Y
3 2 1

Score:
4.94