← 返回题目列表

AtCoder · relay2_d

D. 震惊

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

分数: 100 点

问题陈述

给你一个无向图 G. G 有 N 顶点和 M 边缘。顶点编号从 1 通过 N,以及 i第边缘 (1 ≤ i ≤ M) 连接顶点 a_i 和 b_i. G 没有自环和多重边。

您可以重复执行在两个顶点之间添加边的操作。然而, G 不得产生自循环或多重边。另外,如果顶点 1 和 2 通过边缘直接或间接连接,您的身体将暴露在 1000000007 伏。这也必须避免。

在这些条件下,最多可以添加多少条边?注意顶点 1 和 2 从一开始就从未直接或间接连接。

约束

  • 2 ≤ N ≤ 10^5
  • 0 ≤ M ≤ 10^5
  • 1 ≤ a_i < b_i ≤ N
  • 所有对 (a_i, b_i) 是不同的。
  • 顶点 1 和 2 in G 不通过边直接或间接连接。

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1
:
a_M b_M

输出

打印可添加的最大边缘数。


示例输入 1

4 1
1 3

示例输出 1

2

如上所示,可以添加两条边。不可能添加三个或更多边。


示例输入 2

2 0

示例输出 2

0

无法添加边。


示例输入 3

9 6
1 4
1 8
2 5
3 6
4 8
5 7

示例输出 3

12