// http://w...content-available-to-author-only...c.jp/k1sakai/Lecture/ALG/2012/ALG2012-B.pdf p.7
#include <bits/stdc++.h>
using namespace std;
short currseq;
vector<short> seq;
vector<bool> artic;
int dfs(vector<vector<int>>& g, int v)
{
seq[v]=++currseq;
int m=currseq;
for(int u: g[v]) {
if (!seq[u]) {
int k=dfs(g, u);
m=min(m, k);
bool f=false;
if (seq[v]==1)
f=(seq[u]!=2);
else
f=(k>=seq[v]);
if (f) artic[v]=true;
}
else if (seq[u]<m) {
m=seq[u];
}
}
return m;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T; cin>>T;
while (T--) {
int n, m, k;
cin>>n>>m>>k;
vector<vector<int>> g(n);
seq=vector<short>(n);
artic=vector<bool>(n);
currseq=0;
while (m--) {
int a, b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(g, 0);
cout<<count(begin(artic), end(artic), true)*k<<endl;
}
}
Ly8gaHR0cDovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmMuanAvazFzYWthaS9MZWN0dXJlL0FMRy8yMDEyL0FMRzIwMTItQi5wZGYgcC43CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc2hvcnQgY3VycnNlcTsKdmVjdG9yPHNob3J0PiBzZXE7CnZlY3Rvcjxib29sPiBhcnRpYzsKCmludCBkZnModmVjdG9yPHZlY3RvcjxpbnQ+PiYgZywgaW50IHYpCnsKICAgIHNlcVt2XT0rK2N1cnJzZXE7CiAgICBpbnQgbT1jdXJyc2VxOwogICAgZm9yKGludCB1OiBnW3ZdKSB7CiAgICAgICAgaWYgKCFzZXFbdV0pIHsKICAgICAgICAgICAgaW50IGs9ZGZzKGcsIHUpOwogICAgICAgICAgICBtPW1pbihtLCBrKTsKICAgICAgICAgICAgYm9vbCBmPWZhbHNlOwogICAgICAgICAgICBpZiAoc2VxW3ZdPT0xKQogICAgICAgICAgICAgICAgZj0oc2VxW3VdIT0yKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgZj0oaz49c2VxW3ZdKTsKICAgICAgICAgICAgaWYgKGYpIGFydGljW3ZdPXRydWU7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKHNlcVt1XTxtKSB7CiAgICAgICAgICAgIG09c2VxW3VdOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBtOwp9CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwoKICAgIGludCBUOyBjaW4+PlQ7CiAgICB3aGlsZSAoVC0tKSB7CiAgICAgICAgaW50IG4sIG0sIGs7CiAgICAgICAgY2luPj5uPj5tPj5rOwogICAgICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZyhuKTsKICAgICAgICBzZXE9dmVjdG9yPHNob3J0PihuKTsKICAgICAgICBhcnRpYz12ZWN0b3I8Ym9vbD4obik7CiAgICAgICAgY3VycnNlcT0wOwogICAgICAgIHdoaWxlIChtLS0pIHsKICAgICAgICAgICAgaW50IGEsIGI7IGNpbj4+YT4+YjsKICAgICAgICAgICAgZ1thXS5wdXNoX2JhY2soYik7CiAgICAgICAgICAgIGdbYl0ucHVzaF9iYWNrKGEpOwogICAgICAgIH0KICAgICAgICBkZnMoZywgMCk7CiAgICAgICAgY291dDw8Y291bnQoYmVnaW4oYXJ0aWMpLCBlbmQoYXJ0aWMpLCB0cnVlKSprPDxlbmRsOwogICAgfQp9Cg==