Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
1 #include <bits/stdc++.h> 2 using namespace std; 3 int f[50010],fi[50010],ne[60010][2],n,m,a[50010],q1[50010],fa[50010],q2[50010],tot,x,y,fi1[50010],ne1[50010][2],tot1,fi2[50010],ne2[50010][3],tot2,jl,cl; 4 bool bz[50010],bz1[50010]; 5 void add(int x,int y){ 6 ne[++tot][0]=fi[x]; 7 ne[tot][1]=y; 8 fi[x]=tot; 9 } 10 void add1(int x,int y){ 11 ne1[++tot1][0]=fi1[x]; 12 ne1[tot1][1]=y; 13 fi1[x]=tot1; 14 } 15 void add2(int x,int y,int bz){ 16 ne2[++tot2][0]=fi2[x]; 17 ne2[tot2][1]=y; 18 ne2[tot2][2]=bz; 19 fi2[x]=tot2; 20 } 21 void dfs1(int top,int x){ 22 add2(top, x, 1); 23 if (fa[x]==top){ 24 q2[top]+=q1[x]+1, q1[x]=min(q1[x], 1+q2[x]); 25 return; 26 } 27 q1[fa[x]]=q1[x]+q2[fa[x]]+1; 28 dfs1(top, fa[x]); 29 q1[x]=min(q1[x], q1[fa[x]]+q2[x]+1); 30 } 31 void dfs(int x){ 32 if (x==16){ 33 x++;x--; 34 } 35 bz[x]=1; 36 int i=fi[x]; 37 while (i){ 38 if (!bz1[i]){ 39 bz1[i]=bz1[i^1]=1; 40 if (bz[ne[i][1]]){ 41 add1(ne[i][1], x), jl++; 42 } 43 else{ 44 int zhi=jl-cl; 45 dfs(ne[i][1]); 46 fa[ne[i][1]]=x; 47 if (jl-cl==zhi) add2(x, ne[i][1], 0), q1[ne[i][1]]=1; 48 } 49 } 50 i=ne[i][0]; 51 } 52 bz[x]=0; 53 i=fi1[x]; 54 while (i){ 55 q1[ne1[i][1]]=1+q2[ne1[i][1]]; 56 dfs1(x, ne1[i][1]); 57 cl++; 58 i=ne1[i][0]; 59 } 60 i=fi2[x]; 61 while (i){ 62 if (ne2[i][2]) f[x]=max(f[x], f[ne2[i][1]]+q2[x]-q1[ne2[i][1]]); 63 else f[x]=max(f[x], q2[x]+f[ne2[i][1]]+1); 64 i=ne2[i][0]; 65 } 66 f[x]=max(f[x], q2[x]); 67 } 68 int main(){ 69 scanf("%d%d", &n, &m); 70 tot=1; 71 for (int i=1; i<=m; i++){ 72 scanf("%d%d", &x, &y); 73 add(x, y); add(y, x); 74 } 75 dfs(1); 76 printf("%d", f[1]); 77 }