题目描述

本题的前两段（不包括本段）与“Juggle Struggle: Part 2”完全相同。除此之外，这两道题可以独立解决；你无需阅读或解决其中一道题即可理解或解决另一道题。

作为 Graceful Chainsaw Jugglers 团队的经理，你决定让表演更加精彩。你不再让每位杂技演员单独抛接自己的电锯，而是让他们两两组队，每对互相抛接电锯。在这种新表演中，将有 $2 \times \mathbf{N}$ 名杂技演员同时登台，被分为 $\mathbf{N}$ 对，每位杂技演员恰好属于一对。

你认为，如果不同对的杂技演员所抛接的电锯有相互碰撞的风险，表演会更加惊险。设舞台为一个二维平面，连接一对杂技演员位置的直线段称为该对的抛接路径。当两条抛接路径相交时，称这两对杂技演员的电锯存在碰撞风险。我们称杂技演员的空间位置及其配对方式为一种“安排”。如果每两对杂技演员的电锯都存在碰撞风险，则称该安排为“壮观的安排”。

经过长时间的思考和设计，你想出了一个壮观的安排，并把杂技演员在舞台上的位置和配对方式记录在纸上。不幸的是，一次失误的电锯抛掷把纸张切成了两半，你丢失了记载配对方式的那一半。由于舞台布景已经根据杂技演员的位置设计好，这些位置无法更改。距离备受期待的首演只剩下几个小时，你需要重新找到一个壮观的安排！给定每位杂技演员在二维舞台上的位置，请找出一种配对方式，使得该安排是壮观的。

输入格式

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示杂技演员对数。接下来的 $2 \times \mathbf{N}$ 行，每行包含两个整数 $\mathbf{X}_\mathbf{i}$ 和 $\mathbf{Y}_\mathbf{i}$，表示第 $i$ 位杂技演员的位置坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: $j_1$ $j_2$ $\dots$ $j_{2 \times \mathbf{N}}$，表示第 $i$ 位杂技演员应与第 $j_i$ 位杂技演员配对，对于每个 $i$ 都满足 $j_{j_i} = i$。

输入输出样例 #1

输入 #1

3
2
-1 -1
-1 1
1 1
1 -1
3
1 2
2 1
2 3
3 1
3 3
4 2
3
7 1
1 1
7 2
5 5
3 5
1 2

输出 #1

Case #1: 3 4 1 2
Case #2: 6 5 4 3 2 1
Case #3: 5 4 6 2 1 3

说明/提示

样例解释

在样例第 1 个测试用例中，杂技演员的位置构成一个正方形。唯一的有效方案是将第 1 位与第 3 位配对，第 2 位与第 4 位配对。

数据范围

• $-10^9 \leq \mathbf{X}_\mathbf{i} \leq 10^9$，对所有 $i$ 成立。
• $-10^9 \leq \mathbf{Y}_\mathbf{i} \leq 10^9$，对所有 $i$ 成立。
• 任意三位杂技演员的位置不共线。（这也意味着没有两位杂技演员处于同一位置。）
• 至少存在一种配对方式，使得最终安排是壮观的。

测试点 1（5 分，公开）

• 时间限制：20 秒。
• $1 \leq \mathbf{T} \leq 100$。
• $2 \leq \mathbf{N} \leq 100$。

测试点 2（30 分，隐藏）

• 时间限制：60 秒。
• $1 \leq \mathbf{T} \leq 10$。
• $2 \leq \mathbf{N} \leq 10^5$。