题目描述

有一个 $n$ 个点 $m$ 条边的无向图，小 F 想给每条边定一个方向，使得这个图变为一个有向无环图。定向的方案可能很多，于是她希望这个有向无环图的最长路径能最短（注：路径的长度定义为该路径包含的边数）。

输入格式

第一行两个整数 $n,m$ ，表示无向图的点数和边数。

接下来 $m$ 行，每行两个整数 $u,v$ 表示无向图中的一条边。

保证给出的无向图无重边无自环。

输出格式

一行一个整数表示最短的最长路径长度。

样例

3 3
1 2
2 3
1 3

2

数据范围与约定

对于 $10\%$ 的数据， $n\leq 8,m\leq 20$ 。

对于 $20\%$ 的数据， $n\leq 10$ 。

对于 $40\%$ 的数据， $n\leq 12$ 。

对于 $60\%$ 的数据， $n\leq 14$ 。

对于 $100\%$ 的数据， $n\leq 17,m\leq \frac{1}{2}n(n-1)$ 。