Description

对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。

Input

在文本文件 worm.in 中第一行两个整数 N ， M ，分别表示树中结点个数和树的边数。

接下来 M 行，每行两个整数 a, b 表示点 a 和点 b 有边连接（ a, b ≤ N ）。你可以假定没有一对相同的 (a, b) 会出现一次以上。

Output

在文本文件 worm.out 中写入一个整数 , 表示最大的毛毛虫的大小。

Sample Input

13 12

1 2

1 5

1 6

3 2

4 2

5 7

5 8

7 9

7 10

7 11

8 12

8 13

Sample Output

11

Hint

40% 的数据， N ≤ 50000

100% 的数据， N ≤ 300000

Solution

维护包含该点的子树内最大毛毛虫，答案统计时为子树内最大毛毛虫+次大毛毛虫的结果。时间复杂度为O(n).

Code

#include <stdio.h>

#define MN 300005

#define R register

#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);

#define end fclose(stdin);fclose(stdout)

inline int read(){

	R int x; R bool f; R char c;

	for (f=0; (c=getchar())<'0'||c>'9'; f=c=='-');

	for (x=c-'0'; (c=getchar())>='0'&&c<='9'; x=(x<<3)+(x<<1)+c-'0');

	return f?-x:x;

}

int f[MN],ans,n,to[MN<<1],nt[MN<<1],h[MN],en,sz[MN];

inline void ins(int x,int y){to[++en]=y,nt[en]=h[x],h[x]=en;++sz[x];}

inline int max(int a,int b){return a>b?a:b;}

inline void dfs(int u,int fa){

	R int ma1=0,ma2=0;f[u]=1;

	for (R int i=h[u]; i; i=nt[i])

		if (to[i]!=fa){

			dfs(to[i],u);

			if (f[to[i]]>ma1) ma2=ma1,ma1=f[to[i]];

			else if (f[to[i]]>ma2) ma2=f[to[i]];

		}f[u]=max(f[u],ma1+sz[u]-1);ans=max(ans,ma2+ma1+sz[u]-1);

}

int main(){

	n=read(),read();

	for (R int i=1; i<n; ++i){

		R int x=read(),y=read();

		ins(x,y);ins(y,x);

	}dfs(1,0);printf("%d\n",ans);

}