当前没有测试数据。

问题描述

用以太网线缆将 $n$ 台计算机连接成一个网络，计算机的编号从 $0$ 到 $n-1$。

有 $m$ 条线缆将其中一部分计算机两两连接在一起。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 $-1$ 。

格式

输入

第一行为两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行两个整数 $a$ 和 $b$，表示计算机 $a,b$ 通过一根线缆连接。

输出

一个整数，表示使计算机全部连通所需的最少操作次数。 如果不可能，输出 $-1$。

样例

4 3
0 1
0 2
1 2

1

6 5
0 1
0 2
0 3
1 2
1 3

2

6 4
0 1
0 3
1 2

-1

5 4
0 1
0 2
3 4
2 3

0

提示

样例说明

• 样例一如下图，可拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上：
• 样例二如下图：
• 样例三线缆数量不足。
• 样例四无需操作

数据范围

• $1 <= n <= 10^5$
• $1 <= m <= min(n*(n-1)/2, 10^5)$
• 没有重复的连接。
• 两台计算机不会通过多条线缆连接。