题目描述

無向グラフ $G$ が与えられます。$G$ は $N$ 個の頂点と $M$ 本の辺を持ちます。$G$ の頂点には $1$ から $N$ までの番号が付けられており、$G$ の $i$ 番目の辺 $(1\ <\ =\ i\ <\ =\ M)$ は頂点 $a_i$ と $b_i$ を結びます。$G$ は自己辺や多重辺を持ちません。

あなたは、$G$ の二頂点間に辺を付け足す操作を繰り返し行うことができます。ただし、その結果 $G$ が自己辺や多重辺を持ってはなりません。また、頂点 $1$ と $2$ が直接的または間接的に辺で結ばれてしまうと、あなたの身体を $1000000007$ ボルトの電圧が襲います。これも避けなければなりません。

これらの条件のもとで、最大で何本の辺を付け足すことができるでしょうか？なお、頂点 $1$ と頂点 $2$ がはじめから直接的または間接的に辺で結ばれていることはありません。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $:$ $a_M$ $b_M$

输出格式

付け足すことのできる辺の本数の最大値を出力せよ。

题目大意

一个无向图 $G$ 中有 $n$ 个点和 $m$ 条边，无向图中的点被依次编号为 $1$ ， $2$ ， $3$ ，…… ， $n$ 。

请求出最多可以添加几条边，使得编号为 $1$ 的点和编号为 $2$ 的点不连通。

4 1
1 3

2

2 0

0

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

12

提示

制約

• $2\ <\ =\ N\ <\ =\ 10^5$
• $0\ <\ =\ M\ <\ =\ 10^5$
• $1\ <\ =\ a_i\ <\ b_i\ <\ =\ N$
• 組 $(a_i,\ b_i)$ はすべて異なる。
• $G$ の頂点 $1,$ $2$ は直接的にも間接的にも辺で結ばれていない。

Sample Explanation 1

 上図のように、$2$ 本の辺を付け足すことができます。$3$ 本以上の辺を付け足すことはできません。

Sample Explanation 2

 辺を付け足すことはできません。