| 41 | } |
| 42 | |
| 43 | int main() |
| 44 | { |
| 45 | fastio //faster input and output |
| 46 | int q; |
| 47 | cin>>q; |
| 48 | for(int i=0; i<q; i++) |
| 49 | { |
| 50 | ll n,m,l,r; |
| 51 | cin>>n>>m>>l>>r; |
| 52 | // graph is represented using adjaceny list |
| 53 | vector<ll>* graph= new vector<ll> [n](); |
| 54 | ll u1,v1; |
| 55 | for(ll j=0; j<m; j++) |
| 56 | { |
| 57 | cin>>u1>>v1; |
| 58 | graph[u1-1].push_back(v1-1); |
| 59 | graph[v1-1].push_back(u1-1); |
| 60 | } |
| 61 | // Case1 - Cost of library is less than cost of repairing the road |
| 62 | if(l<=r) |
| 63 | { |
| 64 | ll ans = n*l; |
| 65 | cout<<ans<<endl; |
| 66 | continue; |
| 67 | } |
| 68 | // Case2 - Cost of library is greater than cost of repairing the road |
| 69 | // visited array to mark the visited nodes during traversal |
| 70 | bool* visited = new bool[n](); |
| 71 | ll ans = 0; |
| 72 | for(ll i=0;i<n;i++) |
| 73 | { |
| 74 | // call dfs for each unvisted node |
| 75 | if(!visited[i]){ |
| 76 | // total cost = summation of (l + (cc-1)*r) for each component. |
| 77 | ans += l; |
| 78 | ans += (dfs(graph,visited,i)-1)*r; |
| 79 | } |
| 80 | } |
| 81 | cout<<ans<<endl; |
| 82 | } |
| 83 | } |