配点 : $100$ 点

問題

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

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

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

制約

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

入力

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

$N$ $M$

$a_1$ $b_1$

$:$

$a_M$ $b_M$

出力

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

4 1
1 3

2

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

2 0

0

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

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

12