题目描述

一场自行车比赛将在一个国家举行。全国的交通网络由 $n$ 个城市组成，编号为 $1\sim n$，由 $m$ 条双向道路连接。我们定义以下术语：

• 一条路线是一系列道路，当且仅当这些道路每条都从上一条道路的结束城市出发。

• 一条简单路线是指一条不经过一个城市一次以上的道路。

• 环是一条起点与终点相同的简单路线。

对于任意两个城市之间，保证至少有一条路线，且每条整个交通系统中的每条道路最多是一个环的一部分。

你的任务是找到满足以下两个约束条件的最长路线：

• 路线可以从任何城市开始，但必须在城市 $1$ 结束。

• 这条路线可以多次访问同一个城市，但不能经过同一条道路超过一次。

请你输出最长的路线的长度。

输入格式

输入第一行为两个整数 $n,m$，表示城市的数量和道路的数量。

接下来的 $m$ 行，每行两个整数 $a,b$，描述一条连接 $a,b$ 的双向道路。

保证不会出现两个城市直接由多条道路连接。

输出格式

输出最长路线的长度。

4 3
1 2
1 3
2 4

2

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

5

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

6

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le n\le 10^4$，$1\le m\le 2n-2$，$1\le a,b\le n$。

说明

题目译自 COCI2007-2008 CONTEST #1 T6 STAZA