问题 4037. -- 喵呜的旅行

4037: 喵呜的旅行

时间限制: 1 Sec  内存限制: 128 MB
献花: 7  解决: 2
[献花][花圈]

题目描述

喵呜突然想去拜访许久不见的皮卡丘。电脑前面待久了,出去一趟总想游览一番。于是喵呜骑上他的草泥马自西向东(皮卡丘居住的城市在喵呜的东边)开始他的拜访之旅。
既然想游览当然想经过更多的城市,但是马粮又很贵,所以喵呜决定不经过同一个城市两次(除了喵呜所在城市),并且不走回头路(拜访皮卡丘的路上不往家的方向走,回家的路上不往皮卡丘家的方向走)!
为了简化问题,我们假定喵呜可能经过的城市自西向东排开。喵呜的家在最西边,皮卡丘的家在最东边。将城市自西向东,从1到N编号。
喵呜出发前用他6400+MHz的大脑心算出了结果。你知道喵呜最多能经过多少城市吗?

输入

多组测试数据
第1行两个正整数N(2<=N<=100),M(1<=M<=4950)。N表示有N个城市。
接下来M行每行两个正整数x,y(1<=x,y<=N)。表示编号x的城市和编号y的城市有路连通。

输出

一个正整数,喵呜能经过城市的最大值。如果找不到可行路径输出1。

样例输入

8 9
1 3
1 4
4 5
5 6
6 8
7 8
3 7
3 2
3 4

样例输出

7

提示

喵呜拜访皮卡丘并回到自己家才算可行路径。喵呜所在城市计算一次。

来源

[献花][花圈]