P13002 [GCJ 2022 Finals] Goose, Goose, Ducks?

首届国际鹅类大会刚刚结束，尽管这本应是一件值得高兴的事，却让人五味杂陈。组织者发现了一份文件，详细记录了鸭子的渗透计划。现在，他们正试图从与会者中找出这群渗透者。 找到的文件中包含 $\mathbf{M}$ 个整数三元组 $(\mathbf{X}_i, \mathbf{Y}_i, \mathbf{C}_i)$，表示鸭子们会在会议开始后恰好 $\mathbf{C}_i$ 秒在点 $(\mathbf{X}_i, \mathbf{Y}_i)$ 处集合，该点位于会议大厅中心以东 $\mathbf{X}_i$ 米、以北 $\mathbf{Y}_i$ 米处。每只鹅可能在这些特定时间出现在这些特定地点，也可能没有，但每只鸭子一定都在。 鸭子和鹅的最大行走速度均为每秒 1 米，这意味着在时间 $t$ 处于点 $(x, y)$ 的与会者可以在时间 $t + \Delta_t$ 前到达任何形如 $(x + \Delta_x, y + \Delta_y)$ 的点，只要满足 $\Delta_x^2 + \Delta_y^2 \leq \Delta_t^2$。每位与会者在时间 0 时的位置可以是任意点，与其他与会者无关。  发现文件后，组织者召开了一场质询会以试图识别鸭子。在质询过程中，与会者依次发表了一系列声明。按发表顺序，第 $j$ 条声明由与会者 $\mathbf{A}_j$ 作出，声称他们和与会者 $\mathbf{B}_j$ 在会议开始后恰好 $\mathbf{D}_j$ 秒时位于点 $(\mathbf{U}_j, \mathbf{V}_j)$。声明中的点可能是也可能不是鸭子集合的地点。 **鹅的声明总是真实的，但鸭子可能撒谎**。此外，鸭子知道哪些与会者是鸭子，哪些是鹅。为了避免轻易暴露，鸭子只会发表与之前鹅作出的所有声明一致的声明。注意，鹅的声明与所有鸭子都参加了所有鸭子集合是一致的。 根据提供的信息，可能无法确定所有鸭子。然而，知道鸭子的最小数量至少可以为鸭子活动的活跃程度提供一个下限。注意，至少存在一只鸭子。请找出这一最小数量。 形式化地，假设 $H$ 是将所有与会者划分为鸭子集合（称为 $H$-鸭子）和鹅集合（称为 $H$-鹅）的一种分类。$H$ 与一组声明 $S$ 一致的条件是：存在每位与会者以不超过每秒 1 米的速度移动的路径，满足： * 所有 $H$-鸭子都参加了所有鸭子集合； * 对于 $S$ 中每一条声称 $A$ 在时间 $T$ 于点 $P$ 看到 $B$ 的声明，$A$ 和 $B$ 的路径在时间 $T$ 都经过点 $P$。 假设 $H$ 在一组声明 $S$ 下是可行的，如果： * $H$-鸭子非空（即至少存在一只鸭子）， * $S$ 中由 $H$-鹅成员作出的所有声明的子集与 $H$ 一致（即鹅的声明总是真实的）， * 对于 $S$ 中由 $H$-鸭子成员作出的每一条声明 $s$，如果 $P \subseteq S$ 是在 $s$ 之前由 $H$-鹅成员作出的声明的子集，则存在一个假设 $H'$（可能与 $H$ 相同也可能不同）使得 $\{s\} \cup P$ 与 $H'$ 一致（即鸭子不会与之前鹅的声明矛盾）。 注意，$H$-鸭子包含所有与会者的假设 $H$ 总是可行的。 求出所有可行假设 $H$ 中 $H$-鸭子集合的最小大小。

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含三个整数 $\mathbf{N}$、$\mathbf{M}$ 和 $\mathbf{S}$，分别表示与会者数量、鸭子集合数量和声明数量。接下来的 $\mathbf{M}$ 行每行描述一个鸭子集合，包含三个整数 $\mathbf{X}_i$、$\mathbf{Y}_i$ 和 $\mathbf{C}_i$，表示在点 $(\mathbf{X}_i, \mathbf{Y}_i)$ 处有一个集合，时间为会议开始后恰好 $\mathbf{C}_i$ 秒。然后，每个测试用例的最后 $\mathbf{S}$ 行描述声明。第 $j$ 行描述第 $j$ 条声明，包含五个整数 $\mathbf{A}_j$、$\mathbf{B}_j$、$\mathbf{U}_j$、$\mathbf{V}_j$ 和 $\mathbf{D}_j$，表示与会者 $\mathbf{A}_j$ 声称他们和与会者 $\mathbf{B}_j$ 在会议开始后恰好 $\mathbf{D}_j$ 秒时位于点 $(\mathbf{U}_j, \mathbf{V}_j)$。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是可能渗透会议的最小鸭子数量。

**样例解释** 在样例 #1 中，与会者 1 是唯一的鸭子是一个可行的假设。 在样例 #2 中，与会者 2 和 4 是唯一的鸭子是一个可行的假设。注意，至少存在一只鸭子，因此所有与会者都是鹅的假设不可行。 **限制条件** - $1 \leq \mathbf{T} \leq 50$。 - $-10^9 \leq \mathbf{X}_i \leq 10^9$，对所有 $i$。 - $-10^9 \leq \mathbf{Y}_i \leq 10^9$，对所有 $i$。 - $1 \leq \mathbf{C}_i \leq 10^9$，对所有 $i$。 - $\mathbf{C}_i < \mathbf{C}_{i+1}$，对所有 $i$。 - $(\mathbf{X}_i - \mathbf{X}_{i+1})^2 + (\mathbf{Y}_i - \mathbf{Y}_{i+1})^2 \leq (\mathbf{C}_i - \mathbf{C}_{i+1})^2$，对所有 $i$。 - $1 \leq \mathbf{A}_j \leq \mathbf{N}$，对所有 $j$。 - $1 \leq \mathbf{B}_j \leq \mathbf{N}$，对所有 $j$。 - $\mathbf{A}_j \neq \mathbf{B}_j$，对所有 $j$。 - $-10^9 \leq \mathbf{U}_j \leq 10^9$，对所有 $j$。 - $-10^9 \leq \mathbf{V}_j \leq 10^9$，对所有 $j$。 - $1 \leq \mathbf{D}_j \leq 10^9$，对所有 $j$。 - $(\mathbf{A}_j, \mathbf{B}_j, \mathbf{U}_j, \mathbf{V}_j, \mathbf{D}_j) \neq (\mathbf{A}_k, \mathbf{B}_k, \mathbf{U}_k, \mathbf{V}_k, \mathbf{D}_k)$，对所有 $j \neq k$。 **测试集 1（11 分，可见判定）** - 时间限制：20 秒。 - $2 \leq \mathbf{N} \leq 50$。 - $1 \leq \mathbf{M} \leq 50$。 - $1 \leq \mathbf{S} \leq 50$。 **测试集 2（24 分，隐藏判定）** - 时间限制：60 秒。 - $2 \leq \mathbf{N} \leq 10^5$。 - $1 \leq \mathbf{M} \leq 10^5$。 - $1 \leq \mathbf{S} \leq 10^5$。 翻译由 DeepSeek V3 完成