题目描述

一个城市有 $N$ 个公交站和 $M$ 条双向道路。任意两座公交站之间至多有一条直接道路。

一条公交线路必须是一条简单环：

• 至少经过 3 个不同的公交站；
• 除起点与终点相同外，不重复经过公交站；
• 相邻两个公交站之间必须有道路。

城市开设了尽可能多的不同公交线路，并且任意两条公交线路至少有一条使用的道路不同。也就是说，每一个由道路构成的不同简单环都对应一条公交线路。

现在要安排一天中的公交检查计划。

设所有公交线路编号为 $1,2,\ldots,K$。检查计划可以看作一个表格：

• 每一列对应一条公交线路；
• 每一行对应一个检查时刻；
• 单元格中的数字 $X$ 表示在这个时刻，于公交站 $X$ 检查该线路上的公交车；
• 单元格也可以为空。

计划必须满足：

1. 每一条公交线路在一天中必须在它经过的每一个公交站恰好被检查一次；
2. 同一时刻，同一个公交站不能检查两辆公交车；
3. 同一辆公交车在同一时刻不可能位于两个不同公交站。

请计算完成全部检查所需的最少检查时刻数，也就是计划表的最少行数。

输入格式

第一行两个整数：

N M

其中：

接下来 $M$ 行，每行两个整数：

u v

表示公交站 $u$ 和 $v$ 之间有一条双向道路。

保证没有自环和重边。

输出格式

输出一个整数，表示最少需要多少个检查时刻。

样例输入

4 4
1 2
2 3
1 3
1 4

样例输出

3