#include <iostream> #include<vector> using namespace std; void dfs(int i, vector< vector<int> > adj, bool visited[], int dis[], int low[], int parent[], bool ap[]){ static int d =0; visited[i] = 1; int child = 0; dis[i] = low[i] = ++d; for(int j = 0;j < adj[i].size();j++){ // cout<<"hey"<<" "; if(visited[adj[i][j]] == 0){ child++; parent[adj[i][j]] = i; dfs(adj[i][j],adj,visited,dis,low,parent,ap); low[i] = min(low[i],low[adj[i][j]]); if(parent[i] == i && child>1){ ap[i] = true; } if( parent[i] != i && low[adj[i][j]] >= dis[i]){ ap[i] = true; } } else{ if(adj[i][j] != parent[i]){ low[i] = min(low[i],dis[adj[i][j]]); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int test; cin>>test; while(test--){ int n,m,k; cin>>n>>m>>k; // cout<<"hey"<<endl; bool *visited = new bool[n]; int *dis = new int[n]; int *low = new int[n]; int *parent = new int[n]; bool *ap = new bool[n]; for(int i = 0;i < n;i++){ parent[i] = i; dis[i] = 0; low[i] = 0; ap[i]= false; visited[i] = 0; } vector <vector <int> > adj(n+1,vector<int>()); for(int i = 0; i < m;i++){ int x,y; cin>>x>>y; adj[x].push_back(y); adj[y].push_back(x); } if(m == n*(n-1)/2){ cout<<"0"<<endl; continue; } int cnt = 0; dfs(0,adj,visited,dis,low,parent,ap); for(int i = 0; i < n;i++){ if(ap[i] == true){ // cout<<"hey"<<endl; cnt++; } } //cout<<cnt<<endl; cout<<cnt*k<<endl; } return 0; }