题目链接：https://ac.nowcoder.com/acm/problem/14545
思路：用并查集将关系网捋清楚，筛选出小d关系网内的人。然后后续问题就是01背包问题了，即代价C内，如何交际才能使价值最大。
并查集所用的就是两个最基础的find 和merge 操作，就不必多说了。
01背包也是最简单的dp问题了 。
话不多说，贴代码，很多细节在注释中。

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define ll long long
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
int n, m, c;
const int maxn = 10005;
int cost[maxn], value[maxn];
int fa[maxn];
int dp[505];
int find(int x) {  
    return(fa[x]==x?x:fa[x]=find(fa[x]));
}
void merge(int x, int y) { //将x 和y合并到一个关系网内
    fa[find(x)] = find(y);
}
void my_input(void) {
    cin >> n >> m>>c;
    for (int i = 2;i <= n;i++) { cin >> cost[i] >> value[i]; }
}
void solve(void) {
    memset(dp, 0, sizeof(dp));
    for (int i = 1;i <= n;i++) { fa[i] = i; } //首先将n个人初始化为n张互相独立的关系网 以便后期合并
    while (m--) { //合并各个关系网
        int x, y;
        cin >>x >> y;
        merge(x, y);
    }
    //合并完以后转变为dp 问题  对于和1（小d自己）在一个关系网内的人  交际每一个人都有一个对应的代价和一个对应的价值 在总代价C内 使得价值最大
    //dp[x]表示代价为x内可获得的最大价值
    for (int i = 2;i <= n;i++) {
        if (find(i) == find(1)) {
            for (int j = c;j >= cost[i];j--) { dp[j] = max(dp[j], dp[j - cost[i]] + value[i]); }
        }
    }
    cout << dp[c] << "\n";
}
int main() {
    close_stdin;//这个只是为了让cin和printf一样快而已
    int T;
    cin >> T;
    while (T--) {
        my_input();
        solve();
    }
}