题目描述

Ada 住在一个魔法国家 $A$，她在魔法大学学习。今天，Ada 想在一个特殊空间中收集魔法点。

这个空间有 $N$ 个房间（编号 $0, 1, \ldots, N - 1$）。有 $M$ 条走廊连接这些房间。走廊 $j$ 连接房间 $X_j$ 和 $Y_j$，即你可以在两个房间之间移动。

第 $i$ 个房间包含 $A_i$ 个魔法点，并且受到一个具有属性 $L_i$ 和 $R_i$ 的魔法护盾的保护。要进入第 $i$ 个房间，首先你需要通过已经破盾的房间到达与第 $i$ 个房间相邻的任意房间（即通过走廊相连的房间）。然后你必须打破该房间的护盾，但只有当你的魔法点数在 $L_i$ 和 $R_i$ 之间（包含两端）时，你才能打破护盾。打破护盾后，你将进入该房间并自动收集该房间的 $A_i$ 个魔法点。房间不会生成新的魔法点。护盾被打破后也不会再生，因此无论你当前有多少点数，你都可以自由返回所有已经破盾的房间。

Ada 开始时拥有 $0$ 个魔法点，她的目标是找到一种方法恰好收集 $K$ 个魔法点。她可以在任意房间开始，也可以在任意房间结束。她选择的起始房间的魔法护盾会自动被打破，并且她会自动收集该房间的所有魔法点。

在查看了房间和走廊的地图后，Ada 认为任务太简单了，因此她想挑战一个更困难的任务：她想知达到目标有多少种不同的方式。如果两条路径的唯一路径不同，则认为它们是不同的。唯一路径是指她打破护盾的房间顺序（去除重复），例如：如果你按顺序访问房间 $(1, 3, 2, 1, 3, 5, 3, 6)$，则唯一路径为 $(1, 3, 2, 5, 6)$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含三个整数 $N$、$M$ 和 $K$：房间的数量、走廊的数量以及要收集的魔法点数。

接下来的 $N$ 行，每行包含三个整数 $L_i$、$R_i$ 和 $A_i$：第 $i$ 个房间的魔法护盾属性 $L_i$ 和 $R_i$，以及该房间的魔法点数 $A_i$。

接下来的 $M$ 行，每行包含两个整数 $X_j$ 和 $Y_j$：走廊 $j$ 连接的两个房间。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是收集 $K$ 个魔法点的方式数量。

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

Case #1: 4
Case #2: 8
Case #3: 4

提示

在第一个测试用例中，有 $4$ 种不同的方式，如下图所示：

:::align{center} :::

在第二个测试用例中，有 $8$ 种不同的方式，如下图所示：

:::align{center} :::

在第三个测试用例中，有 $4$ 种不同的方式，如下图所示：

:::align{center} :::

限制条件

$1 \le T \le 100$。

$0 \le M \le \frac{N \times (N-1)}{2}$。

$0 \le X_j, Y_j \le N - 1$。

$X_j \ne Y_j$。

每对房间之间至多有一条走廊。

测试集 1

$1 \le N \le 8$。

$1 \le K \le 100$。

$0 \le L_i \le R_i \le 50$。

$1 \le A_i \le 50$。

测试集 2

$1 \le N \le 15$。

$1 \le K \le 2 \times 10^9$。

$0 \le L_i \le R_i \le 10^9$。

$1 \le A_i \le 10^9$。

翻译由 DeepSeek V4 Pro 完成