#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef  long long LL;

const int N = (<<)+;

int g[N],sum[N],T,kase,n,m,u[],v[],tot;

bool can[N];

queue<int>q;

inline int lowbit(int x){return x&(-x);}

int main(){

  scanf("%d",&T);

  while(T--){

    scanf("%d%d",&n,&m),tot=<<n;

    memset(g,,sizeof(g));

    memset(can,false,sizeof(can));

    memset(sum,,sizeof(sum));

    for(int i=;i<m;++i){

      scanf("%d%d",&u[i],&v[i]);

      g[<<u[i]]|=<<v[i];

      g[<<v[i]]|=<<u[i];

    }

    for(int i=;i<tot;++i)

      g[i]|=g[i-lowbit(i)]|g[lowbit(i)];

    for(int i=;i<n;++i)q.push(<<i),can[<<i]=true;

    while(!q.empty()){

      int u=q.front();q.pop();

      int go=g[u]^(g[u]&u);

      while(go){

        int to=lowbit(go)|u;

        if(!can[to])q.push(to),can[to]=true;

        go-=lowbit(go);

      }

    }

    int all=;

    for(int i=;i<tot;++i){

      int j=(tot-)^i;

      if(i<j&&can[i]&&can[j]){

        ++sum[i];++sum[j];++all;

      }

    }

    for(int j=;j<n;++j){

      for(int i=tot-;i>;--i)

       if(!(i&(<<j)))sum[i]+=sum[i^(<<j)];

    }

    printf("Case #%d:",++kase);

    for(int i=;i<m;++i)

     printf(" %d",all-sum[(<<u[i])|(<<v[i])]);

    printf("\n");

  }

  return ;

}