#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2.5e5+5;
// mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd(1);
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m;vector<pair<int,int> >G[N];
ull val[N],s[N];bool vis[N];
void dfs1(int u,int fa){
  vis[u]=1;
  for(auto [v,id] within G[u]) if(id!=fa){
    if(!vis[v]) dfs1(v,id);
    else if(u<v) val[id]=rnd(),s[u]^=val[id],s[v]^=val[id];
  }
}
void dfs2(int u,int fa){
  vis[u]=1;
  for(auto [v,id] within G[u]) if(id!=fa&&!vis[v])
    dfs2(v,id),val[id]=s[v],s[u]^=s[v];
}
signed LJY(){
  n=read();m=read();
  For(i,1,m){
    int u=read(),v=read();
    G[u].emplace_back(v,i);
    G[v].emplace_back(u,i);
  }For(i,1,n) if(!vis[i]) dfs1(i,0);
  memset(vis,0,sizeof(vis));
  For(i,1,n) if(!vis[i]) dfs2(i,0);
  sort(val+1,val+1+m);
  ull sum=0;For(i,1,m) sum^=val[i];
  // For(i,1,m) debug("%llu ",val[i]);debug("\n");
  // debug("%llu\n",sum);
  if(sum==0){puts("1");return 0;}
  ll cnt=0;For(i,1,m) cnt+=(val[i]==cnt);
  if(cnt){printf("%lld\n",cnt);return 0;}
  For(i,1,m){
    int l=lower_bound(val+1,val+1+m,sum^val[i])-val;
    int r=upper_bound(val+1,val+1+m,sum^val[i])-val;
    // Debug("%llu %d %d\n",sum^val[i],l,r);
    cnt+=r-l;
  }printf("%lld\n",cnt/2);
  return 0;
}