Problem: You are given an undirected graph G. G has N vertices and M edges. The vertices are numbered from 1 through N, and the i-th edge (1 ≤ i ≤ M) connects Vertex a_i and b_i. G does not have self-loops and multiple edges.

You can repeatedly perform the operation of adding an edge between two vertices. However, G must not have self-loops or multiple edges as the result. Also, if Vertex 1 and 2 are connected directly or indirectly by edges, your body will be exposed to a voltage of 1000000007 volts. This must also be avoided.

Under these conditions, at most how many edges can you add? Note that Vertex 1 and 2 are never connected directly or indirectly in the beginning.

Constraints

* 2 ≤ N ≤ 10^5
* 0 ≤ M ≤ 10^5
* 1 ≤ a_i < b_i ≤ N
* All pairs (a_i, b_i) are distinct.
* Vertex 1 and 2 in G are not connected directly or indirectly by edges.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_M b_M


Output

Print the maximum number of edges that can be added.

Examples

Input

4 1
1 3


Output

2


Input

2 0


Output

0


Input

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


Output

12

Solution (in CPP):

Solution:
// 基本テンプレート
 
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;
 
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// Union-Find 木 (Verified: AtCoder Typical Contest 001 B)
struct UnionFind {
private:
    const int n;
    int __size;
    vector<int> uf, edge_cnt;
public:
    // 初期化 UnionFind uni(n) のように宣言すれば良い
    UnionFind(int _n) : n(_n), __size(_n), uf(_n, -1), edge_cnt(_n, 0) {}
    // find (木の根を求める)
    int find(int x) {return (uf[x] < 0) ? x : uf[x] = find(uf[x]);}
    // x と y が同じ集合に属するかどうか
    bool same(int x, int y) {return find(x) == find(y);}
    // x が属する集合の要素数
    int size(int x) {return -uf[find(x)];}
    // 集合はいくつあるか
    int size()      {return __size;}
    int edge(int x) {return edge_cnt[find(x)];}
    // x と y の属する集合を併合
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if(x == y) {
            edge_cnt[x]++;
            return;
        }
        __size--;
        if(uf[y] < uf[x]) swap(x, y);
        uf[x] += uf[y]; edge_cnt[x] += edge_cnt[y] + 1; uf[y] = x;
    }
};

int N, M;
 
signed main() {
    cin >> N >> M;

    UnionFind uf(N);
    rep(i,0,M) {
        int u, v; cin >> u >> v;
        u--; v--;
        uf.unite(u, v);
    }

    int vertices = max(uf.size(0), uf.size(1));
    set<int> S;
    S.insert(uf.find(0));
    S.insert(uf.find(1));

    int ans = 0;
    rep(k,0,2) {
        int V = uf.size(k);
        int comp = V * (V - 1) / 2;
        // printf("k = %lld, rest = %lld\n", k, comp - uf.edge(k));
        ans += comp - uf.edge(k);
    }

    int V = 0, E = 0;
    rep(i,2,N) {
        int f = uf.find(i);
        if(S.count(f)) continue;
        S.insert(f);
        // printf("find %lld (size = %lld)\n", i+1, uf.size(i));
        ans += uf.size(i) * vertices;

        V += uf.size(i);
        E += uf.edge(i);
    }
    int comp = V * (V - 1) / 2;
    ans += comp - E;

    cout << ans << endl;
    return 0;
}