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]);
}