P13152 [GCJ 2018 #3] Fence Construction

你是一名“Fence Construction Company”（围栏建造公司）的员工，被分配去建造 $F$ 段围栏。每段围栏都是一条从一个点到另一个点的直线段。形式化地说，每段围栏是连接二维平面上两个不同点的线段。围栏之间不会相互相交，除了可能在端点处。所有围栏是连通的，即对于任意两段围栏 $f$ 和 $g$，都存在一条路径 $f = f_1, f_2, \dots, f_k = g$，使得 $f_i$ 与 $f_{i+1}$ 共享一个端点。 在你开始工作时，尚未建造任何围栏。建造工作通过一种特殊的“围栏发射”3D 打印机完成。只有一台这样的设备，因此围栏需要一段一段地建造。打印机足够小，可以视为平面上的一个点。 要建造某段围栏 $f$，你必须首先将打印机放置在平面上的某个点 $p$，使得打印机能够“看到”整个 $f$，且视线不会被之前建造的围栏阻挡。形式化地说，$p$ 必须满足： - $p$ 不能在 $f$ 上（包括端点）。 - 对于 $f$ 上的任意非端点 $q$，连接 $p$ 和 $q$ 的线段不能与任何已建造的围栏相交。 移动打印机时，你可以从当前位置沿着一条连续但不一定直的路径移动，只要这条路径不与任何已建造的围栏相交（包括端点）。在建造第一段围栏之前和最后一段围栏之后，你可以选择打印机的任意位置。 由于需要遵循上述流程，你并不总能以任意顺序建造围栏。例如，你可能选择了一个顺序，结果把打印机困在某处，无法移动到需要的位置。 公司主管已经为 $K$ 段围栏指定了一个相对顺序（但这些围栏都还未建造），但他并未深思熟虑。为了避免惹怒主管，你需要遵循这个顺序，并将剩下的 $F-K$ 段围栏插入到任意位置以完成整个顺序。 在这些限制下，请找出一种建造围栏的顺序。保证至少存在一种合法的顺序。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为两个整数 $F$ 和 $K$，分别表示围栏总数和主管指定顺序中的围栏数。接下来 $F$ 行，第 $i$ 行（从 1 开始计数）包含四个整数 $A_i$、$B_i$、$C_i$ 和 $D_i$，表示第 $i$ 段围栏是从点 $(A_i, B_i)$ 到 $(C_i, D_i)$ 的线段。输入中的前 $K$ 段围栏即为主管指定顺序中的围栏。

对于每组测试数据，输出一行，格式为 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为一个用空格分隔的 $1$ 到 $F$ 的整数排列，表示一种合法的建造围栏顺序。

**样例解释** 注意，最后一个样例不会出现在测试集 1 中。 在样例 1 中，可以按给定顺序建造围栏：$1, 2, 3, 4, 5, 6$。注意，围栏 $1$ 必须在围栏 $2$ 之前建造，这是主管的要求。 在样例 2 中，无法按给定顺序建造围栏！一种可行的顺序是：$5, 6, 1, 2, 3, 4$。注意，当主管指定的顺序只包含一段围栏时，相对顺序条件总是自动满足。 在样例 3 中，可以按顺序建造：$11, 10, 7, 8, 9, 1, 2, 3, 6, 5, 4$。注意，围栏 $1, 2, 3, 4$ 必须按这个相对顺序建造。 下图展示了样例 1 的一种合法建造方式。    **数据范围** - $1 \leq T \leq 100$。 - $4 \leq F \leq 300$。 - $-10^5 \leq A_i \leq 10^5$，对所有 $i$。 - $-10^5 \leq B_i \leq 10^5$，对所有 $i$。 - $-10^5 \leq C_i \leq 10^5$，对所有 $i$。 - $-10^5 \leq D_i \leq 10^5$，对所有 $i$。 - $(A_i, B_i) \neq (C_i, D_i)$，对所有 $i$。 - 如果 $p$ 是某段围栏上的非端点，则 $p$ 不是任何其他围栏上的点。 - 给定的围栏是连通的，如题目描述所定义。 - 至少存在一种满足所有建造限制的围栏顺序。 **测试集 1（12 分，公开）** - $1 \leq K \leq 2$。 **测试集 2（23 分，隐藏）** - $1 \leq K < F$。 由 ChatGPT 4.1 翻译