P12959 [GCJ Farewell Round #3] The Decades of Coding Competitions

自 **Sphinny** 通过掌握竞赛排程的艺术成为顶尖编程选手以来，已经过去了近 15 年。她与 **Coding Competitions** 一同成长，并转型为一名编程竞赛组织者，而她创立的 **Programming Club League (PCL)** 已成为她所在城市最受欢迎的运动。 **Sphinny** 的城市中有 $\mathbf{N}$ 个公交站点和 $\mathbf{M}$ 条快速公交线路。每条线路双向连接两个不同的公交站点（称为端点）。由于 **PCL** 的流行，每条公交线路的司机恰好为一个俱乐部加油。 **Sphinny** 需要在第 $j$ 场比赛前从公交站点 $\mathbf{P}_j$ 取比赛材料，然后在公交站点 $\mathbf{C}_j$ 举办比赛。她只能使用给定的公交线路在两者之间通行。形式上，**Sphinny** 从 $\mathbf{P}_j$ 到 $\mathbf{C}_j$ 的路径是一个公交线路列表，其中每两条相邻线路有一个共同的端点，且第一条线路的端点为 $\mathbf{P}_j$，最后一条线路的端点为 $\mathbf{C}_j$。注意，同一条公交线路可以在路径中多次使用。如果 **Sphinny** 从 $\mathbf{P}_j$ 到 $\mathbf{C}_j$ 的路径中包含一条或多条司机为俱乐部 $c$ 加油的公交线路，则俱乐部 $c$ 会参加比赛；否则，俱乐部 $c$ 不会参加比赛。出于组织原因，**Sphinny** 需要每场比赛参加的俱乐部数量为奇数。 给定 **Sphinny** 所在城市的公交线路布局和比赛详情，计算有多少场比赛存在一条路径，使得参加的俱乐部数量为奇数。

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。 每个测试用例的第一行包含三个整数 $\mathbf{N}$、$\mathbf{M}$ 和 $\mathbf{Q}$，分别表示公交站点的数量、公交线路的数量和比赛的数量。 接下来是 $\mathbf{M}$ 行，每行表示一条公交线路。第 $i$ 行包含三个整数 $\mathbf{U}_i$、$\mathbf{V}_i$ 和 $\mathbf{K}_i$，表示第 $i$ 条公交线路连接公交站点 $\mathbf{U}_i$ 和 $\mathbf{V}_i$，且其司机为俱乐部 $\mathbf{K}_i$ 加油。 最后是 $\mathbf{Q}$ 行，每行表示一场比赛。第 $j$ 行包含两个整数 $\mathbf{P}_j$ 和 $\mathbf{C}_j$，表示第 $j$ 场比赛的材料需要在公交站点 $\mathbf{P}_j$ 取，并在公交站点 $\mathbf{C}_j$ 举办比赛。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足条件的比赛数量。

**样例解释**  样例 #1 如上图所示。在前两场比赛中，无论选择哪条路径，两个俱乐部（绿色和蓝色）都必须参加。对于最后一场比赛，可以通过路径 $1, 2, 4, 5$ 仅让绿色俱乐部参加。 对于样例 #2，第一场比赛无法进行，因为没有从公交站点 $1$ 到 $2$ 的路径。第二场比赛有一条路径包含从公交站点 $1$ 到 $3$ 的唯一公交线路，因此恰好有 $1$ 个俱乐部参加，这是一个可接受的奇数。 以下附加样例（样例组 #2）符合测试集 2 的限制，但不会用于测试您的提交。  此附加样例如上图所示。在这种情况下，两场比赛均可通过奇数个俱乐部完成。图中展示了一条满足条件的路径。 **限制** - $1 \leq \mathbf{T} \leq 100$。 - 对于所有 $i$，$1 \leq \mathbf{U}_i \leq \mathbf{N}$。 - 对于所有 $i$，$1 \leq \mathbf{V}_i \leq \mathbf{N}$。 - 对于所有 $i$，$\mathbf{U}_i \neq \mathbf{V}_i$。 - 对于所有 $i \neq j$，$(\mathbf{U}_i, \mathbf{V}_i) \neq (\mathbf{U}_j, \mathbf{V}_j)$ 且 $(\mathbf{U}_i, \mathbf{V}_i) \neq (\mathbf{V}_j, \mathbf{U}_j)$。（没有两条公交线路具有相同的端点对。） - 对于所有 $j$，$1 \leq \mathbf{P}_j \leq \mathbf{N}$。 - 对于所有 $j$，$1 \leq \mathbf{C}_j \leq \mathbf{N}$。 - 对于所有 $j$，$\mathbf{P}_j \neq \mathbf{C}_j$。 **测试集 1（7 分，可见评测结果）** - 时间限制：20 秒。 - $2 \leq \mathbf{N} \leq 500$。 - $1 \leq \mathbf{M} \leq 500$。 - $1 \leq \mathbf{Q} \leq 500$。 - 对于所有 $j$，$1 \leq \mathbf{K}_j \leq 2$。 **测试集 2（6 分，可见评测结果）** - 时间限制：40 秒。 - $2 \leq \mathbf{N} \leq 500$。 - $1 \leq \mathbf{M} \leq 500$。 - $1 \leq \mathbf{Q} \leq 500$。 - 对于所有 $j$，$1 \leq \mathbf{K}_j \leq 100$。 **测试集 3（10 分，隐藏评测结果）** - 时间限制：120 秒。 - $2 \leq \mathbf{N} \leq 10000$。 - $1 \leq \mathbf{M} \leq 10000$。 - $1 \leq \mathbf{Q} \leq 10000$。 - 对于所有 $j$，$1 \leq \mathbf{K}_j \leq 100$。 翻译由 DeepSeek V3 完成