说明

阿里亚德娜知道，部分读者之间本就是朋友或熟人，因此彼此存有对方的电子邮箱地址。她认为，打造这个社群的良好开端，是让所有人都拥有其他所有人的邮箱地址，这样每个人都能联系到整个群体。由于她了解自己博客的读者也非常喜欢以 “去中心化” 的方式行事，于是她设计了如下协议，将于第 $D$ 天启动：

• 每天早上 $8$ 点，所有人都会将自己通讯录中当前的联系人列表发送给通讯录里的每一位联系人。
• 每天晚上 $8$ 点，所有人都会更新自己的通讯录，添加所有新收到的邮箱地址。

如果某人在晚上 8 点无需进行任何更新，那么就称该流程对这个人而言已 “收敛”，此后她无需在后续日子里继续发送邮件。

你是一名技艺高超的黑客，设法获取了该博客所有读者的通讯录权限。你想给阿里亚德娜一个惊喜，告知她其提出的这套流程是否能让所有人最终都获得其他人的地址。此外，如果流程能成功，你还需要为她准确估算所需天数。更具体地说，若流程成功，你可以选择给出以下任一数值：

• 直至最后一次更新发生时所经过的天数 $E$（包含第一天）；
• 直至流程在所有人端都收敛时所经过的天数（包含第一天）。请注意，根据阿里亚德娜的定义，该数值等于 $E + 1$。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$，分别对应读者数量和初始时互有对方邮箱地址的读者对数。读者编号从 $1$ 到 $N$。

接下来 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示读者 $i$ 和读者 $j$ 初始时互有对方的邮箱地址（即读者 $i$ 存有读者 $j$ 的地址，且读者 $j$ 也存有读者 $i$ 的地址）。

输出格式

输出仅包含一个整数：

• 若流程无法让所有人最终获得其他人的地址，输出 $-1$；
• 否则输出估算所需的天数（该数值可以为 $0$）。

4 3
1 2
2 3
3 4

2

6 3
1 2
3 4
5 6

-1

提示

数据范围

• $2\leq N\leq 10^5$
• $1\leq M\leq 10^5$
• 我们假设读者群体是稳定的，即整个流程期间无读者退出、也无新读者加入。
• 我们假设所有人都知晓自己的邮箱地址；收到自己的地址会被直接忽略。
• 你无需在不同测试用例间保持答案的 “一致性”，即可以在某个测试用例中输出 $E$，在另一个测试用例中输出 $E+1$。

样例 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$ 也同样正确。