Time Limits: 1000 ms Memory Limits: 65536 KB

Description

翠亨村举行一场自行车赛,翠亨村有N个路口(编号1到N),另有M条双向边连接起来。下面有几个定义:
  •路径:由一系列边组成,满足后一条边的起点为前一条边的终点;
  •简单路径:每个路口最多经过一次的路径;
  •环:起点和终点在同一个路口的简单路径。
  保证每对路口之间至少有一条路径相连,除此之外还满足每条边最多只会出现在一个环中。
  你的任务是找出最长的满足以下两个条件的路径:
  •起点可以在任意路口,但终点必须在1号路口;
  •路径可能多次经过同一个路口,但每条边最多只会经过一次。

Input

第一行包含两个整数N和M(2<=N<=10000,1<=M<=2N-2),表示路口数量和边的数量。
  接下来M行,每行包含两个不同的整数A和B(1<=A,B<=N),表示A和B之间存在一条边直接相连,两个路口之间最多只有一条边直接相连。

Output

输出最长的比赛路径的长度。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入1:
4 3
1 2
1 3
2 4

输入2:
6 6
1 2
1 3
2 4
3 4
3 5
5 6

输入3:
5 6
1 2
2 3
3 4
4 5
5 3
3 1

Sample Output

1
2
3
4
5
6
7
输出1:
2

输出2:
5

输出3:6

Code

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