题目描述

从前有个包含$\red{n}$个点，$\red{m}$条边，无自环和重边的无向图。

对于两个没有直接连边的点$\red{u}$;$\red{v，}$你可以将它们合并。具体来说，你可以删除$\red{u}$;$\red{v}$及所有以它们作为端点的边，然后加入一个新点$\red{x，}$将它与所有在原图中与$\red{u}$或$\red{v}$有直接连边的点连边。

你需要判断是否能通过若干次合并操作使得原图成为一条链，如果能，你还需要求出这条链的最大长度

输入格式

从文件$\red{merge.in}$中读入数据。

第一行两个正整数$\red{n}$;$\red{m，}$表示图的点数和边数。

接下来$\red{m}$行，每行两个正整数$\red{u}$;$\red{v，}$表示$\red{u}$和$\red{v}$之间有一条无向边

输出格式

输出到文件$\red{merge.out}$中。

如果能通过若干次合并操作使得原图成为一条链，输出链的最大长度，否则输出$\red{-1}$

样例

输入样例1

5 4

1 2

2 3

3 4

3 5

输出样例1

3

输入样例2

4 6

1 2

2 3

1 3

3 4

2 4

1 4

输出样例2

-1

提示

对于$\red{30\%}$的数据，$\red{n<=10}$

对于$\red{70\%}$的数据，$\red{m<=2000}$

对于$\red{100\%}$的数据，$\red{n<=1000,m<=10^5}$