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>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/12/04  Problem: codefestival2017_team_relay D / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,s,t) for(int (i)=(s);(i)<(t);(i)++)



/* Union Find */
struct UnionFind {
	vector<int> data;
	UnionFind(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};
// UnionFind uf(n); uf.unionSet(i,j); if(uf.same(x,y))



LL N,M;

LL ans = 0LL;


void dfs(int v,int p , VI& used, VVI &G){
	used[v] = 1;
	FOR(i,0,SZ(G[v])){
		if(p!=G[v][i]&&used[G[v][i]]==0)
			dfs(G[v][i],v,used,G);
	}
	
}


int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	UnionFind uf(N);
	LL ret = 0;
	vector<vector<int > >G(N,VI());
	FOR(i, 0, M){
		int a, b; cin>> a >> b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
		uf.unionSet(a,b);
	}
	
	VI used(N,0);
	priority_queue<PLL>q;
	VI aa(2,0);
	FOR(i,0,N){
		if(used[i]==1)continue;
		LL S = uf.size(i);
		dfs(i,-1,used,G);
		ret += S*(S-1)/2LL;
		if(i>=2)q.push(PII(S,i));
		else aa[i] = S;
		//debug(S);
		//debug(i);
		used[i]=1;
	}
	//debug(aa[0]);
	//debug(aa[1]);
	int id = aa[1]>aa[0];
	q.push(PII(aa[id],id));
	//  ０，１に気をつけながらでっかいものにマージ
	while(q.size()>1){
		PII a = q.top();q.pop();
		PII b = q.top();//q.pop();
		
		int as = a.first;
		int av = a.second;
		int bs = b.first;
		int bv = b.second;
		if((av ==0 && bv==1)||(av ==1 && bv == 0)){
			q.push(a);
		}else {
			q.pop(); // b
	//		cout<<av<<";"<<as<<"--"<<bv<<";"<<bs<<endl;
			ret += as* bs;
			q.push(PII(as+bs,min(av,bv)));
		}
		
	}
	
	// つかったものは使わない
	
	ans = ret - M;
	cout << ans << "\n";

	return 0;
}