Ariadna 的博客里充满了美味的食谱和关于健康平衡生活的明智建议。不出所料，它因此吸引了大量的读者。目前读者群已经稳定，Ariadna 觉得如果能让他们有更多的互动并形成一个更紧密的社区，而不是仅仅依赖于博客，会很有用。
Ariadna 知道一些读者已经是朋友或熟人，因此拥有彼此的电子邮件地址。她认为，发展社区的一个良好开端是让每个人都拥有其他所有人的电子邮件地址，这样每个人都能联系到整个群体。由于她知道她的博客读者也非常喜欢以“去中心化”的方式做事，因此她设计了以下协议，从第 $D$ 天开始执行：
- 每天早上 8 点，每个人将通讯录中的当前联系人列表发送给通讯录中的所有联系人。
- 每天晚上 8 点，每个人更新自己的通讯录，添加任何新收到的电子邮件地址。
如果一个人在晚上 8 点不需要进行任何更新，则称该过程对这个人已经“收敛”（converged），此后她将不再需要在接下来的日子里继续发送电子邮件。
你是一名技术高超的黑客，已经设法获取了所有博客读者的通讯录。你希望通过告知 Ariadna 她提出的过程是否会导致每个人最终都拥有其他所有人的地址来给她一个惊喜。此外，如果该过程注定会成功，你希望给她一个关于需要多少天的大致估计。更准确地说，如果过程成功，你可以给她：
- 直到最后一次更新发生所经过的天数 $E$（包括第一天），或者
- 直到过程在每个人那边都收敛所经过的天数（包括第一天）。注意，根据 Ariadna 的定义，这等于 $E+1$。
输入格式
输入的第一行包含两个整数 $N$ 和 $M$，分别对应读者的数量和最初拥有彼此电子邮件地址的读者对的数量。读者编号从 1 到 $N$。
接下来的 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示读者 $i$ 和读者 $j$ 最初拥有彼此的电子邮件地址。注意，这意味着读者 $i$ 拥有读者 $j$ 的地址，且读者 $j$ 拥有读者 $i$ 的地址。
输出格式
输出应包含一个整数，等于： $-1$，如果该过程最终不能使每个人都拥有其他所有人的电子邮件地址，或者 估计所需的必要天数。注意，这个数字可能等于 0。
说明
- 我们假设读者群是稳定的，即在整个过程中没有读者离开，也没有额外的读者加入。
- 我们假设每个人都知道自己的电子邮件地址；收到自己的地址会被直接忽略。
- 你不需要在多个测试用例中保持“一致”，这意味着你可以为一个测试用例输出值 $E$，而为另一个输出 $E+1$。
数据范围
- $2 \leqslant N \leqslant 100\,000$
- $1 \leqslant M \leqslant 100\,000$
样例
样例输入 1
4 3 1 2 2 3 3 4
样例输出 1
2
样例说明 1
该过程进行如下：
- 在第 $D$ 天早上 8 点：
- 读者 1 将读者 2 的地址发送给读者 2。
- 读者 2 将读者 1 和 3 的地址发送给读者 1 和 3。
- 读者 3 将读者 2 和 4 的地址发送给读者 2 和 4。
- 读者 4 将读者 3 的地址发送给读者 3。
- 在第 $D$ 天晚上 8 点更新后：
- 读者 1 的通讯录已更新，包含读者 2 和 3 的地址。
- 读者 2 的通讯录已更新，包含读者 1、3 和 4 的地址。
- 读者 3 的通讯录已更新，包含读者 1、2 和 4 的地址。
- 读者 4 的通讯录已更新，包含读者 2 和 3 的地址。
- 在第 $D+1$ 天早上 8 点：
- 读者 1 将读者 2 和 3 的地址发送给读者 2 和 3。
- 读者 2 将读者 1、3 和 4 的地址发送给读者 1、3 和 4。
- 读者 3 将读者 1、2 和 4 的地址发送给读者 1、2 和 4。
- 读者 4 将读者 2 和 3 的地址发送给读者 2 和 3。
- 在第 $D+1$ 天晚上 8 点更新后：
- 读者 1 的通讯录已更新，包含读者 2、3 和 4 的地址。
- 该过程对读者 2 已经收敛，因为没有更新。
- 该过程对读者 3 已经收敛，因为没有更新。
- 读者 4 的通讯录已更新，包含读者 1、2 和 3 的地址。
- 在第 $D+2$ 天早上 8 点：
- 读者 1 将读者 2、3 和 4 的地址发送给读者 2、3 和 4。
- 读者 4 将读者 1、2 和 3 的地址发送给读者 1、2 和 3。
- 在第 $D+2$ 天晚上 8 点更新后：
- 该过程对读者 1 已经收敛，因为没有更新。
- 该过程对读者 4 已经收敛，因为没有更新。
最后一次更新发生在第 $D+1$ 天，经过了 2 天。该过程在第 $D+2$ 天对每个人都收敛，经过了 3 天。样例输出包含前者，即 2。输出后者，即 3，也是同样正确的替代方案。
样例输入 2
6 3 1 2 3 4 5 6
样例输出 2
-1
Figure 1. Illustration of the email exchange process