Description

自 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 所在城市的公交线路布局和比赛详情，计算有多少场比赛存在一条路径，使得参加的俱乐部数量为奇数。

Input Format

输入的第一行给出测试用例的数量 $\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$ 举办比赛。

Output Format

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

2
5 5 3
1 2 1
2 3 2
2 4 1
2 5 1
4 5 1
1 3
3 4
5 1
3 1 2
1 3 1
1 2
1 3

Case #1: 1
Case #2: 1

1
4 5 2
1 2 3
1 3 3
3 4 7
2 3 3
2 4 6
1 2
1 4

Case #1: 2

Hint

样例解释

样例 #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 完成