某个国家正在举办一场自行车比赛。该国的交通网络由 $N$ 个城市（编号为 $1$ 到 $N$）和连接它们的 $M$ 条双向道路组成。我们将使用以下术语：

• 路径（path）是指一个道路序列，其中每条道路的起点都是前一条道路的终点。
• 简单路径（simple path）是指不重复访问任何城市的路径。
• 环（ring）是指起点和终点为同一个城市的简单路径。

该网络满足任意两个城市之间至少存在一条路径。此外，网络中的每条道路最多属于一个环。

你的任务是寻找一条满足以下两个约束条件的最长赛跑路径：

• 路径可以从任意城市开始，但必须在城市 $1$ 结束。
• 路径可以多次访问同一个城市，但不能多次包含同一条道路（即每条道路最多只能经过一次）。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$2 \le N \le 10\,000$，$1 \le M \le 2N-2$），分别表示网络中的城市数量和道路数量。

接下来的 $M$ 行，每行包含两个不同的整数 $A$ 和 $B$（$1 \le A, B \le N$）。这些数字表示城市 $A$ 和城市 $B$ 之间存在一条双向道路。输入保证任意两个城市之间最多只有一条道路直接相连。

输出格式

在单行中输出最长赛跑路径的长度。

样例

输入样例 1

4 3 
1 2 
1 3 
2 4

输出样例 1

2

输入样例 2

6 6 
1 2 
1 3 
2 4 
3 4 
3 5 
5 6

输出样例 2

5

输入样例 3

5 6 
1 2 
2 3 
3 4 
4 5 
5 3 
3 1

输出样例 3

6