← 返回题目列表

AtCoder · arc032_2

B. 道路建设

中文机器翻译题面 查看原题

問題文

木匠大久町镇的道路建设正在进行中。在曹镇 N 交叉路口和 有 M 道路,在两个方向上连接两个不同的交叉路口。 不幸的是,并不总是可以通过公路从一个十字路口行驶到另一个十字路口。

曹先生的建筑公司修建了多条连接不同十字路口的道路。 我希望能够使用该道路从任何N 十字路口前往任何其他十字路口。

需要修建多少条道路才能从任何交叉路口通往任何其他交叉路口?但是,当您可以从现有道路上的任何十字路口前往任何其他十字路口时, 请输出0 。


入力

输入是按以下格式从标准输入给出的。

N M
a_1 b_1
a_2 b_2
:
a_M b_M
  • 1 行中显示了 Cho 镇的交叉路口数量和现有道路的数量。 在 2 整数 N (1 ≦ N ≦ 100,000) 和 M (0 ≦ M ≦ 100,000) 用空格分隔。
  • 2 从行 M 行中,给出了有关现有道路的信息。这几天之一 i 行中,i 路连接 2 代表两个交叉点 2 整数 a_i, b_i (1 ≦ a_i < b_i ≦ N 用空格分隔。
  • 从未给出连接相同交叉路口的道路。也就是说, 对于i,j (1≦i,j≦M) ,i≠j 如果 a_i≠a_j 或 b_i≠b_j 成立。

出力

在第一行打印要新建的道路的最少数量。

不要忘记最后的换行符。


入力例1

4 2
1 2
1 3

出力例1

1

交差点 1、2、3 有道路相连,但没有交叉路口。 4 未连接。例如,一个交叉路口 建造一条连接 1 和 4 的道路就足够了。


入力例2

6 4
1 2
2 3
1 3
5 6

出力例1

2