Rural Planning

You bought a big farmyard and want to fence it in. The yard already holds $N$ fence posts, and your lawyers insist that the fence use every single one of them.

The posts are points in the plane. A fence is an order of all $N$ posts: you run a straight length of fence from the first post to the second, from the second to the third, and so on, and finally from the last post back to the first. The result must be a polygon that never touches itself. Exactly two fence segments meet at each post, and no other point of the plane lies on more than one segment.

You also want the yard to stay big. Let $A$ be the largest area you could enclose if you were allowed to leave some posts out, which is the area of the convex hull of the posts. Your fence has to enclose more than $A / 2$.

The first line contains the number of test cases $T$. Each test case begins with a line containing $N$, the number of posts. The posts are numbered from $0$ to $N - 1$. Each of the next $N$ lines contains two integers $X_i$ and $Y_i$, the coordinates of post $i$.

• The $N$ posts sit at distinct points, and they do not all lie on one line.
• $1 \le T \le 30$
• $3 \le N \le 1000$
• $-50000 \le X_i, Y_i \le 50000$

For each test case, print one line containing "Case #x: ", where $x$ is the test case number starting from 1, followed by $N$ distinct integers from $0$ to $N - 1$ separated by single spaces. They are the posts in fence order, and the last post is joined back to the first.

Many orders give a legal fence, so the one to print is fixed by the following recipe.

Sort the posts by $X$, and by $Y$ when two posts share the same $X$. Call this the post order. Let $L$ be the first post in the post order and let $R$ be the last. Both are corners of the convex hull. Walk the hull boundary counterclockwise: the walk from $L$ to $R$ is the lower chain, and the walk from $R$ to $L$, read backwards, is the upper chain. A post that lies on a hull edge without being a corner belongs to the chain holding that edge, and $L$ and $R$ belong to both chains.

Now build two fences.

• Fence U: $L$, then the rest of the upper chain up to $R$, then every post outside the upper chain in decreasing post order.
• Fence D: $L$, then the rest of the lower chain up to $R$, then every post outside the lower chain in decreasing post order.

Neither fence touches itself, and the one enclosing the larger area always encloses more than $A / 2$. Print that fence in the order just described, starting at $L$. If both fences enclose the same area, print Fence U.

No fence can enclose more than $A$, because every fence stays inside the convex hull of the posts.

The two fences often enclose the same area. On any input where every post lies on the hull boundary, both fences trace the hull itself. When $N = 3$, every order traces the same triangle.