只和连通分量以及度数有关。不同连通分量只要连一条边就够了，连通分量为0的时候要特判。一个连通分量只需看度数为奇的点的数量，两个端点(度数为奇)是必要的。

如果多了，奇点数也一定是2的倍数（一条边增加两个度数，总度数是偶数），把多余的成对奇点连边，一定存在一条欧拉路径。

并查集维护或者dfs都可以。

/**********************************************************      --------------Tyrannosaurus---------              **   author AbyssalFish                                   ***********************************************************/#include
     
      using namespace std;typedef long long ll;int V,E,T;const int maxv = 1001;int pa[maxv], deg[maxv], wei[maxv], odd[maxv];int fd(int x){ return x==pa[x]?x:pa[x]=fd(pa[x]); }bool jot(int a,int b){    int x = fd(a), y = fd(b);    if(x != y){        pa[x] = y;        wei[y] += wei[x];        return true;    }    return false;}int cop;int ver[maxv], sz;void newVertex(int i){    ver[sz++] = i; odd[i] = 0;    pa[i] = i; wei[i] = 1; deg[i] = 0; cop++;}//#define LOCALint main(){#ifdef LOCAL    freopen("in.txt","r",stdin);#endif    int kas = 0;    while(scanf("%d%d%d",&V,&E,&T),V){        memset(wei+1,0,sizeof(int)*V);        cop = 0; sz = 0;        for(int i = 0; i < E; i++){            int a , b; scanf("%d%d",&a,&b);            if(!wei[a]) newVertex(a);            if(!wei[b]) newVertex(b);            deg[a]++; deg[b]++;            if(jot(a,b)) cop--;        }        int ans = E + (cop?cop-1:0);        for(int i = 0; i < sz; i++){            int v = ver[i];            if(deg[v] & 1) odd[fd(v)]++;        }        for(int i = 0; i < sz; i++){            int o = odd[ver[i]];            if(o >= 4) ans += (o>>1) -1;        }        printf("Case %d: %d\n",++kas, ans*T);    }    return 0;}