说明

用以太网线缆将 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 2
0 3
1 2

-1

5 4
0 1
0 2
3 4
2 3

0

提示

样例说明

样例一

拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。

样例二

样例三

线缆数量不足。

数据范围

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