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 <bits/stdc++.h>
 
#include <iostream>
#include <algorithm>
 
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>
 
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>
 
 
using namespace std;
#define int long long
 
typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;
 
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
 
const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll INFLL = 1LL<<62;
const double EPS = 1e-12;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;
 
#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

int n, m;
vector<vector<int>> g(100000 + 5);

struct UnionFind {
    int cnt;                          //uniteの回数
    vector<int> par, rank, e, tree_w;

    UnionFind() {}
    
    UnionFind(int n) : par(n), rank(n, 0), e(n, 0), tree_w(n, 1), cnt(0) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
        }
	}

    int find_set(int now) {
        if (now == par[now]) return now;
        return par[now] = find_set(par[now]);
    }

    void unite(int u, int v) {
        cnt++;  
        int x = find_set(u);
        int y = find_set(v);
        if (x == y) {
			e[x]++;
			return ;
		}
        if (x > y) swap(x, y);
		e[x] += e[y] + 1;
        par[y] = x;
		tree_w[x] += tree_w[y];
    }

    bool same(int u, int v) {
        return find_set(u) == find_set(v);
    }

    int tree_weight(int x){
        return tree_w[find_set(x)];
    }
};

signed main() {	
    cin.tie(0);
    ios::sync_with_stdio(false);
	cin >> n >> m;
	UnionFind uf(n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		uf.unite(a, b);
	}
	int num1 = n - uf.tree_w[1];
	int num2 = n - uf.tree_w[0];
	int ans1 = num1 * (num1 - 1) / 2 - (m - uf.e[1]) + (uf.tree_w[1] * (uf.tree_w[1] - 1) / 2 - uf.e[1]);
	int ans2 = num2 * (num2 - 1) / 2 - (m - uf.e[0]) + (uf.tree_w[0] * (uf.tree_w[0] - 1) / 2 - uf.e[0]);
	cout << max(ans1, ans2) << endl;
}