找到一棵dfs搜索树，给每条非树边一个随机非0权值，每条树边为所有经过它的树边的权值的异或。

那么有2种情况是合法的：

1.一条边权值为0，一条边权值非0。

2.两条边异或和为0。

排序后统计即可，时间复杂度$O(m\log m)$。

 

#include
     
      #include
      
       const int N=2010,M=100010;int n,m,i,j,e[M][2],g[N],v[M<<1],w[M<<1],nxt[M<<1],ed,d[N],dfn,f[N],c0,c1;unsigned long long seed,h[M],tag[N],ans;inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}void dfs(int x){  d[x]=++dfn;  for(int i=g[x];i;i=nxt[i])if(w[i]!=f[x]){    int y=v[i];    if(d[y]&&d[y]<=d[x]){      for(seed=seed*233+17;!seed;seed=seed*233+17);      h[w[i]]=seed,tag[x]^=seed,tag[y]^=seed;    }else if(!d[y])f[y]=w[i],dfs(y);  }}void cal(int x){  for(int i=g[x];i;i=nxt[i])if(f[v[i]]==w[i]&&d[v[i]]>d[x])cal(v[i]),tag[x]^=tag[v[i]];  h[f[x]]=tag[x];}int main(){  read(n),read(m);  for(i=1;i<=m;i++)read(e[i][0]),read(e[i][1]),add(e[i][0],e[i][1],i),add(e[i][1],e[i][0],i);  dfs(1),cal(1);  for(i=1;i<=m;i++)if(h[i])c1++;else c0++;  ans=1ULL*c0*c1;  std::sort(h+1,h+m+1);  for(i=1;i<=m;i=j){    for(j=i;j<=m&&h[i]==h[j];j++);    ans+=1ULL*(j-i)*(j-i-1)/2;  }  return printf("%llu",ans),0;}