SP16242 DTRAP - Dexters Trampoline

德克斯特和他的宿敌曼达克都是休伯尔小学的学生。学校计划组织一次嘉年华活动，邀请 $N$ 名学生参加。本来大家都很期待，但曼达克却计划搞破坏。他了解到学生中存在许多小团体，一个小团体中的学生彼此是朋友，但和其他团体的学生不是。他打算在活动中引发他们之间的矛盾。 参加活动时，所有学生需要排队等待使用蹦床。如果两个不是朋友的学生同时上蹦床就会引发争斗。德克斯特得知了这个计划，同时还得知迪迪又试图闯入他的实验室，因此他不得不紧急回家防御。然而，他也不能让曼达克的破坏计划得逞。 蹦床可以承受的总重量为 $W$ 千克。学生们已经很迫不及待了。为了省时和防止争斗，德克斯特决定选择第一批上蹦床的学生，要求他们的总重量恰好等于 $W$，且组内所有学生互为朋友。你的任务是告诉他有多少种这样的方案。德克斯特只知道 $M$ 对学生之间的朋友关系。

第一行是一个整数 $T$，表示测试用例的数量。接下来是 $T$ 组测试用例。每个测试用例的第一行包含三个整数 $N$、$W$ 和 $M$。紧接着的一行包含 $N$ 个整数，分别表示每个学生的体重。接下来的 $M$ 行，每行有两个整数 $q$ 和 $w$，表示学生 $q$ 和学生 $w$ 是朋友。

对于每个测试用例，输出一个整数，表示可以选择的第一批学生的组合数。

- $1 \leq T \leq 10$ - $1 \leq N \leq 22$ - $1 \leq q, w \leq N$ - $0 \leq M \leq \frac{N \cdot (N+1)}{2}$ - $1 \leq W \leq 1500$ - 每个学生的体重在 $1$ 到 $60$ 之间 假设可以选择的学生数量没有限制，蹦床的唯一限制是最大承重 $W$。 ## 样例输入 ``` 2 10 90 5 20 30 10 20 30 50 40 20 40 50 1 2 2 3 3 4 4 5 9 10 5 57 3 20 10 96 20 1 1 2 2 3 1 3 ``` ## 样例输出 ``` 3 0 ``` ## 解释 对于第一个测试用例，有以下三种组合： 1. 学生 (1, 2, 3, 5) 2. 学生 (2, 3, 4, 5) 3. 学生 (9, 10) 对于第二个测试用例，没有任何组合能使学生的总重量达到 $W$。 **本翻译由 AI 自动生成**