题目描述

首届国际鹅类大会刚刚结束，尽管这本应是一件值得高兴的事，却让人五味杂陈。组织者发现了一份文件，详细记录了鸭子的渗透计划。现在，他们正试图从与会者中找出这群渗透者。

找到的文件中包含 $\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 1 2
1 2 3
1 2 1 1 1
2 1 2 2 2
4 2 4
4 3 10
-4 -3 20
1 3 4 3 11
2 4 0 0 16
3 1 6 3 9
4 2 0 0 16

输出 #1

Case #1: 1
Case #2: 2

说明/提示

样例解释

在样例 #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$。