急急国王修公路
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述


急急国王的国家里有N座城池，标号为，以及M条双向道路，第i条道路（）连接了城池u_i和v_i。

最初，国内的城池被分为一些州，每个州内部的城池互相可达，而任意两个州之间互不可达，即一个州的任意城池与另一个州的任意城池互不可达。

急急国王希望修建一些新道路，使得国民可以从任意一座城池出发，去到所有其他城池（即任意两座城池都是互相可达的）。

由于人力物力的限制，每座城池最多只能再新建一条道路。且为了安全考虑，每个州新修建的道路数量不能过多，否则当一个州被敌国攻陷时，其他州也将面临较大的危机。

现在他想知道，每个州新修建的道路数量最低不超过多少时，可以使得各州互通。

输入描述:

第1行：两个整数N、M（）。

第2~行：共有M行，每行2个整数u、v，表示一条连接u、v的双向道路。

输出描述:

一个整数，表示可以使各州互通时，每个州新修建的道路数量上限的最小值。若无论如何都不能使各州互通，则输出-1。
示例1

输入

复制 
4 2
1 2
3 4

输出

复制 
1
示例2

输入

复制 
5 1
1 2

输出

复制 
-1

备注:

样例1：
最初有两个州，分别为：(1、2)，(3，4)。可以新建一条道路1-3,这样可以使得各州互通，且每个城市新修建的道路数量都不超过1，每个州新修建的道路数量都为1。

若不新修建道路，每个州新修建的道路数量都为0，但是不能使各州互通。因此答案为1。

样例2：
最初有四个州，分别为：(1，2)，(3})，(4)，(5)。可以新建道路：1-3，2-4，此时，每个城池新修建道路数量：1、2、3、4都为1，5为0，已经无法再修建新道路了，但仍无法使各州互通。
可以证明无论如何都无法使得各州互通，因此输出-1。

数据范围：