Description

在不远的将来，位于附近星系的你，想要暂时远离作为 Thundera 星唯一纱线制造商的责任，打算去最让人放松的星球 Care-a-Lot 旅行。为此，你将使用星际传送器网络进行旅行。

传送器是一台漂浮在太空中的小型机器。你可以在太空中的任意位置远程使用它，但由于“传送距离守恒原理”，它只能将你传送到距离该传送器 L1 距离与传送前你到该传送器的 L1 距离完全相同的另一个空间点。两个坐标为 $(x_0, y_0, z_0)$ 和 $(x_1, y_1, z_1)$ 的点之间的 L1 距离定义为 $|x_0 - x_1| + |y_0 - y_1| + |z_0 - z_1|$。不幸的是，你的太空喷气背包坏了，无法靠自身在太空中移动；你只能依靠传送器旅行。你从 Thundera 星出发，可以通过传送器从 Thundera 星传送到某点 $p_1$，再用另一个传送器从 $p_1$ 传送到 $p_2$，以此类推。最后一次传送必须恰好到达 Care-a-Lot 星。

现给定两颗星球及所有可用传送器在三维空间中的坐标，问你是否能仅靠传送器完成这次旅行。如果可以，最少需要多少次传送？（即使两次传送用的是同一个传送器，也要算作两次传送。）

输入给出的所有点坐标均为整数，且在一定范围内。但你可以被传送到中间的任意点（坐标可以是整数也可以是非整数），且你能到达的点的坐标没有范围限制。

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例的数量。接下来有 $\mathbf{T}$ 组测试用例。每组测试用例的第一行为一个整数 $\mathbf{N}$，表示可用传送器的数量。随后有 $\mathbf{N}+2$ 行，每行三个整数 $\mathbf{X_i}$、$\mathbf{Y_i}$ 和 $\mathbf{Z_i}$。第一行为你的家园 Thundera 星的坐标，第二行为目的地 Care-a-Lot 星的坐标，剩下的 $\mathbf{N}$ 行每行表示一个传送器的坐标。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 若无法仅靠传送器从 Thundera 到达 Care-a-Lot，则输出 IMPOSSIBLE，否则输出一个整数，表示到达目的地所需的最少传送次数。

3
1
0 0 0
0 4 0
0 3 0
2
0 0 1
0 0 11
0 0 3
0 0 0
3
0 0 0
6 2 0
6 0 0
3 0 0
6 1 0

Case #1: IMPOSSIBLE
Case #2: 3
Case #3: 2

Hint

样例解释

在样例第 1 组中，唯一的传送器距离 Thundera 星恰好为 $3$，你只能被传送到距离该传送器恰好 $3$ 的其他点。从这些点出发，仍然只能到达距离传送器恰好 $3$ 的点。而 Care-a-Lot 星距离该传送器为 $1$，因此永远无法到达。

在样例第 2 组中，最优策略是：首先用 $(0, 0, 3)$ 号传送器传送到 $(0, 0, 5)$，再用 $(0, 0, 0)$ 号传送器传送到 $(0, 0, -5)$，最后再次用 $(0, 0, 3)$ 号传送器传送到 $(0, 0, 11)$。注意，两次使用 $(0, 0, 3)$ 号传送器时实际传送的距离不同，因为两次出发点距离该传送器不同。另外，这两次操作都要计入传送次数。

在样例第 3 组中，最优策略是：先用 $(3, 0, 0)$ 号传送器传送到 $(6, 0, 0)$，再用 $(6, 1, 0)$ 号传送器传送到 $(6, 2, 0)$。注意，虽然 $(6, 0, 0)$ 处也有一个传送器，但仅仅到达该点并不算使用了这个传送器。

限制条件

• $1 \leq T \leq 100$。
• 对所有 $i \neq j$，$(X_i, Y_i, Z_i) \neq (X_j, Y_j, Z_j)$（任意两个对象的坐标都不相同）。

小数据集（测试集 1 - 可见）

• 时间限制：180 45 秒。
• $1 \leq N \leq 100$。
• 对所有 $i$，$-10^3 \leq X_i \leq 10^3$。
• 对所有 $i$，$-10^3 \leq Y_i \leq 10^3$。
• 对所有 $i$，$-10^3 \leq Z_i \leq 10^3$。

大数据集（测试集 2 - 隐藏）

• 时间限制：360 90 秒。
• $1 \leq N \leq 150$。
• 对所有 $i$，$-10^{12} \leq X_i \leq 10^{12}$。
• 对所有 $i$，$-10^{12} \leq Y_i \leq 10^{12}$。
• 对所有 $i$，$-10^{12} \leq Z_i \leq 10^{12}$。

翻译由 GPT4.1 完成。