题目描述

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

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

你认为，如果不同杂技演员对抛接的电锯有相互碰撞的风险，表演会更加惊险。设舞台为一个二维平面，将一对杂技演员的位置用一条直线段连接，称为该对的“抛接路径”。当两对杂技演员的抛接路径相交时，说明他们抛接的电锯存在碰撞风险。我们将杂技演员的空间位置和分组方式称为一种“安排”。如果每一对杂技演员的抛接路径都与其他每一对的抛接路径相交，则称该安排为“壮观的”。也就是说，要使安排壮观，$\mathbf{N}$ 条抛接路径中的每一条都必须与其他 $\mathbf{N}-1$ 条路径相交（这些交点不必都在同一位置）。

经过最后的调整后，你认为你已经得到了一个壮观的安排。由于准备仓促，你希望编写一个检查程序，判断该安排是否真的壮观。如果不是，则最多有 25 对杂技演员的抛接路径未能与所有其他对的路径相交。你希望你的检查程序能列出所有这些未达标的杂技演员对，供进一步检查。

输入格式

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含一个整数 $\mathbf{N}$，表示杂技演员对的数量。接下来的 $\mathbf{N}$ 行，每行包含四个整数 $\mathbf{X}_\mathbf{i}$、$\mathbf{Y}_\mathbf{i}$、$\mathbf{X'}_\mathbf{i}$、$\mathbf{Y'}_\mathbf{i}$。其中 $(\mathbf{X}_\mathbf{i}, \mathbf{Y}_\mathbf{i})$ 和 $(\mathbf{X'}_\mathbf{i}, \mathbf{Y'}_\mathbf{i})$ 分别表示第 $i$ 对杂技演员两人的坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $y$ 为大写单词 MAGNIFICENT，如果输入表示的是一个壮观的安排；否则，$y$ 应为一个严格递增的整数列表。整数 $i$ 应出现在该列表中，当且仅当第 $i$ 对杂技演员的抛接路径未能与至少一条其他抛接路径相交。

输入输出样例 #1

输入 #1

4
2
-1 -1 -1 1
1 1 1 -1
2
-1 -1 1 1
-1 1 1 -1
4
1 2 4 2
2 1 3 1
2 4 3 0
3 3 2 3
3
1 1 2 2
3 7 4 8
8 3 9 3

输出 #1

Case #1: 1 2
Case #2: MAGNIFICENT
Case #3: 1 2 4
Case #4: 1 2 3

说明/提示

样例解释

• 样例 1 中只有两对杂技演员，他们的抛接路径没有相交。
• 样例 2 中，所有对的抛接路径都两两相交，安排是壮观的。
• 样例 3 中，只有第 3 对的抛接路径与所有其他对的路径都相交。

数据范围

• $-10^9 \leq \mathbf{X}_\mathbf{i} \leq 10^9$，对所有 $i$。
• $-10^9 \leq \mathbf{Y}_\mathbf{i} \leq 10^9$，对所有 $i$。
• $-10^9 \leq \mathbf{X'}_\mathbf{i} \leq 10^9$，对所有 $i$。
• $-10^9 \leq \mathbf{Y'}_\mathbf{i} \leq 10^9$，对所有 $i$。
• 不存在三点共线的情况。（这也意味着没有两名杂技演员处于同一位置。）
• 除至多 25 对杂技演员外，其余所有对的抛接路径都与其他 $\mathbf{N} - 1$ 条路径相交。
• 注意：不一定存在一种分组方式能使安排壮观。

测试点 1（5 分，公开）

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

测试点 2（30 分，隐藏）

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