#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;
const int N=8e5+5,inf=1e9+5;
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,col[N],cnt;
int h[N],ce=1,s,t,cur[N],dep[N];
struct Edge{int v,w,nxt;}e[N];
void addedge(int u,int v,int w){
  e[++ce]={v,w,h[u]};h[u]=ce;
  e[++ce]={u,0,h[v]};h[v]=ce;
}
bool getdep(){
  for(int i=1;i<=t;i++) dep[i]=-1;
  queue<int>q;q.push(s);dep[s]=0;
  while(!q.empty()){
    int x=q.front();q.pop();cur[x]=h[x];
    for(int i=h[x];i;i=e[i].nxt){
      int y=e[i].v,z=e[i].w;
      if(z&&!~dep[y]){dep[y]=dep[x]+1;q.push(y);}
    }
  }return ~dep[t];
}
int getflow(int x,int f){
  if(x==t)return f;int ret=0;
  for(int &i=cur[x];i;i=e[i].nxt){
    int y=e[i].v,z=e[i].w;
    if(z&&dep[y]==dep[x]+1){
      int w=getflow(y,min(f-ret,z));
      e[i].w-=w;e[i^1].w+=w;ret+=w;
      if(ret==f)return ret;
    }
  }return ret;
}
int Dinic(){int ret=0;while(getdep())ret+=getflow(s,inf);return ret;}
struct VecArray{
  int h[N];int ce;struct Edge{int v,nxt;}e[N];
  VecArray(){memset(h,0,sizeof(h));ce=0;}
  void addedge(int u,int v){e[++ce]={v,h[u]};h[u]=ce;}
  void clear(){memset(h,0,sizeof(h));ce=0;}
}G,F,vec,T;
int f[N],dfn[N],idfn[N],cdfn;
int fa[N],Mn[N],sdom[N],idom[N];
ll ans;int siz[N];
void dfs(int u){
  idfn[dfn[u]=++cdfn]=u;
  for(int i=G.h[u];i;i=G.e[i].nxt){
    int v=G.e[i].v;
    if(!dfn[v]) f[v]=u,dfs(v);
  }
}
int find(int x){
  if(fa[x]==x) return x;
  int tmp=find(fa[x]);
  if(dfn[sdom[Mn[fa[x]]]]<dfn[sdom[Mn[x]]]) Mn[x]=Mn[fa[x]];
  return fa[x]=tmp;
}
void build(int s){
  For(i,1,cnt) fa[i]=Mn[i]=sdom[i]=i,idom[i]=dfn[i]=0;
  vec.clear();T.clear();cdfn=0;dfs(s);
  ForDown(i,cdfn,1){
    int u=idfn[i];
    for(int i=vec.h[u];i;i=vec.e[i].nxt){
      int v=vec.e[i].v;find(v);
      if(sdom[Mn[v]]==u) idom[v]=u;
      else idom[v]=Mn[v];
    }if(i==1) continue;
    for(int i=F.h[u];i;i=F.e[i].nxt){
      int v=F.e[i].v;
      if(dfn[v]){
        if(dfn[v]<dfn[sdom[u]]) sdom[u]=v;
        else if(dfn[v]>dfn[u]){
          find(v);
          if(dfn[sdom[Mn[v]]]<dfn[sdom[u]])
            sdom[u]=sdom[Mn[v]];
        }
      }
    }vec.addedge(sdom[u],u);fa[u]=f[u];
  }For(i,2,cdfn) if(idom[idfn[i]]!=sdom[idfn[i]])
    idom[idfn[i]]=idom[idom[idfn[i]]];
  For(i,1,cdfn) T.addedge(idom[idfn[i]],idfn[i]);
}
void getans(int u,bool op,bool flg=1){
  if((u>n&&u<=2*n)||u>2*n+2) flg=0;
  siz[u]=(u>n&&u<=2*n&&col[u-n]==op);
  for(int i=T.h[u];i;i=T.e[i].nxt){
    int v=T.e[i].v;
    getans(v,op,flg);
    if(flg) ans+=(ll)siz[u]*siz[v];
    siz[u]+=siz[v];
  }
}
void color(int u,int c){
  col[u]=c;
  for(int i=G.h[u];i;i=G.e[i].nxt){
    int v=G.e[i].v; if(col[v]==-1) color(v,c^1);}
}
signed LJY(){
  n=read();m=read();
  s=2*n+1,t=s+1;
  For(i,1,m){
    int u=read(),v=read();
    G.addedge(u,v);G.addedge(v,u);
  }memset(col,-1,sizeof(col));For(i,1,n) if(col[i]==-1) color(i,0);
  cnt=2*n+2;
  For(u,1,n) if(col[u]) for(int i=G.h[u];i;i=G.e[i].nxt) addedge(u,G.e[i].v,1);
  For(i,1,n){
    if(col[i]) addedge(s,i,1);
    else addedge(i,t,1);
  }Dinic();G.clear();
  for(int i=h[s];i;i=e[i].nxt){
    int v=e[i].v;
    if(e[i].w){
      G.addedge(s,v+n),G.addedge(v+n,v);
      F.addedge(v+n,s);F.addedge(v,v+n);
    }else{
      F.addedge(s,v+n),F.addedge(v+n,v);
      G.addedge(v+n,s);G.addedge(v,v+n);
    }
  }for(int i=h[t];i;i=e[i].nxt){
    int v=e[i].v;
    if(e[i].w){
      G.addedge(t,v+n),G.addedge(v+n,v);
      F.addedge(v+n,t);F.addedge(v,v+n);
    }else{
      F.addedge(t,v+n),F.addedge(v+n,v);
      G.addedge(v+n,t);G.addedge(v,v+n);
    }
  }
  For(u,1,n) for(int i=h[u];i;i=e[i].nxt) if(e[i].w&&e[i].v<=n){
    G.addedge(u,++cnt);G.addedge(cnt,e[i].v);
    F.addedge(e[i].v,cnt);F.addedge(cnt,u);
  }build(s);
  int cnt1=0,cnt2=0;
  For(i,1,n) if(col[i]&&dfn[i+n]) cnt1++;
  getans(s,1);
  For(i,1,cnt) swap(F.h[i],G.h[i]);
  int p=max(F.ce,G.ce);For(i,1,p) swap(F.e[i],G.e[i]);
  swap(F.ce,G.ce);build(t);
  For(i,1,n) if(!col[i]&&dfn[i+n]) cnt2++;
  getans(t,0);
  printf("%lld\n",(ll)cnt1*cnt2+ans);
  return 0;
}