最大流=最小割，而因为本题点的度数不超过3，所以最小割不超过3，EK算法的复杂度为$O(n+m)$。

通过分治求出最小割树，设$f[i][j][k]$表示最小割为$i$时，$j$点在第$k$次分治过程中是否与$S$连通，$h[i][j]$为$f[i][j][k]$的hash值，那么如果$h[k][i]=h[k][j]$，则说明$i$和$j$之间的最小割不超过$k$。

时间复杂度$O(n(n+m))$，需要大量常数优化。

 

#include
     
      #include
      
       #define N 3010struct E{short u,v,nxt,f;}e[9010];int n,m,i,j,k,a[N],S,T,ed=1,g[N],h[N],q[N],maxflow,ans;unsigned int hash[4][N],pos=1;inline void add(int u,int v,int f){e[++ed].u=u;e[ed].v=v;e[ed].f=f;e[ed].nxt=g[u];g[u]=ed;}inline bool bfs(){  int*l=q,*r=q+1,i;  memset(h+1,-1,sizeof(int)*n);  h[q[0]=S]=0;  while(l
       
        <0&&e[i].f)h[*r++=e[i].v]=i;  return h[T]!=-1;}void solve(int l,int r){  if(l>=r)return;  int i,j;  for(i=2;i<=ed;i++)e[i].f=e[i^1].f=1;  S=a[r],T=a[l],maxflow=0;  while(bfs())for(maxflow++,i=T;i!=S;i=e[j].u)e[j=h[i]].f--,e[j^1].f++;  unsigned int*p=hash[maxflow]+1;  for(pos*=233,i=1;i<=n;p++)if(~h[i++])*p+=pos;  int*L=q+l,*R=q+r,*k=a+l;  while(k<=a+r)if(h[*k]<0)*L++=*k++;else *R--=*k++;  memcpy(a+l,q+l,sizeof(int)*(r-l+1));  solve(l,R-q),solve(L-q,r);}int main(){  scanf("%d%d",&n,&m);  while(m--)scanf("%d%d",&i,&j),add(i,j,1),add(j,i,1);  for(i=1;i<=n;i++)a[i]=i;  solve(1,n);  for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)for(k=0;k<4;k++)if(hash[k][i]!=hash[k][j]){ans+=k;break;}  return printf("%d",ans),0;}