Background

机房的各台计算机要能够直接或间接访问到机房内另外所有的计算机，但由于接线员的粗心，并不能达成这一目标，下面请你帮忙计算一下在不能达成目标时，最少需要移动几条连接线，能达成目标？

Description

用以太网线缆将 \(n\) 台计算机连接成一个网络，计算机的编号从 \(0\) 到 \(n-1\)。这些计算机由 \(m\) 根线缆相连。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并输出使所有计算机都连通所需的最少操作次数。如果不可能，则输出 \(-1\) 。

Format

Input

第一行两个整数计算机的数量\(n\)，连接线的条数\(m\)。
接下来第二行到第\(m+1\)行每行两个整数\(u,v\)(\(0 \leq u,v \lt n\))，表示计算机\(u\)和计算机\(v\)之间有一条线缆连接。

Output

一行一个整数，需要最少的操作次数。

Sample 1

Input

4 3
0 1
0 2
1 2

Output

1

Sample 2

Input

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

Output

2

Limitation

1s, 64MB for each test case.
对于30%的数据，保证\(1 \leq n,m \leq 10\)。
对于100%的数据，保证\(1 \leq n,m \leq 10^5\)且\(m \leq \frac{n(n-1)}{2}\)。
没有重复的连接。
两台计算机不会通过多条线缆连接。

Source

LeetCode