Juggle Struggle: Part 1

The first two paragraphs (not counting this one) of this problem and 'Juggle Struggle: Part 2' are identical. The problems can otherwise be solved independently, so you do not need to read or solve one to read or solve the other.

As manager of the Graceful Chainsaw Jugglers group, you have decided to spice up the show. Instead of having each juggler toss their own chainsaws alone, you want them to form pairs, with each pair throwing chainsaws back and forth to each other. In this new performance, $2 \times N$ jugglers will be on stage at the same time, arranged into $N$ pairs, with each juggler in exactly one pair.

The chainsaws juggled by different pairs are at risk of collision if the pairs' paths cross. The stage is a two-dimensional plane. The straight line segment connecting the two jugglers in a pair is that pair's juggling path. When two juggling paths intersect, the chainsaws of those two pairs are at risk of collision. The positions of the jugglers and their pairings together form an arrangement. An arrangement is magnificent if every two pairs have chainsaws that are at risk of collision.

You found a magnificent arrangement and wrote down the juggler positions and pairings on a piece of paper. A bad chainsaw throw then cut the paper in half, and the half with the pairings was lost. The stage decorations were already designed around the juggler positions, so those positions cannot change. The show debuts in a few hours. Given every juggler's position on the two-dimensional stage, find a pairing that yields a magnificent arrangement.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with one line containing a single integer $N$, the number of pairs. Then $2 \times N$ lines follow. The $i$-th of these lines contains two integers $X_i$ and $Y_i$, the coordinates of the $i$-th juggler.

For each test case, output one line containing Case #x: j1 j2 ... j2×N, meaning jugglers $i$ and $j_i$ are paired together for every $i$. Note that $j_{j_i} = i$ for every $i$.

• $-10^9 \le X_i \le 10^9$ for all $i$.
• $-10^9 \le Y_i \le 10^9$ for all $i$.
• No three juggler positions are collinear. This also means no two jugglers share a position.
• At least one pairing exists that yields a magnificent arrangement.

In Sample Case #1, the jugglers' positions form a square. The only valid solution pairs jugglers 1 and 3, and pairs jugglers 2 and 4.