Code Festival Team Relay (Parallel) - Shock

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from collections import deque
(N, M) = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	es[a].append(b)
	es[b].append(a)
a = b = 1
visited = [1, 1] + [0] * (N - 2)
q = deque([0])
while q:
	fr = q.popleft()
	for to in es[fr]:
		if visited[to]:
			continue
		q.append(to)
		visited[to] = 1
		a += 1
q = deque([1])
while q:
	fr = q.popleft()
	for to in es[fr]:
		if visited[to]:
			continue
		q.append(to)
		visited[to] = 1
		b += 1
if a > b:
	(a, b) = (b, a)
unused = N - a - b
b += unused
ans = a * (a - 1) // 2 + b * (b - 1) // 2 - M
print(ans)


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from functools import *
from itertools import permutations, combinations, groupby
import sys
import bisect
import string
import math
import time
import random

def Golf():
	(*a,) = map(int, open(0))

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}):
	mp = [1] * (w + 2)
	found = {}
	for i in range(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [1] + [mp_def[j] for j in s] + [1]
	mp += [1] * (w + 2)
	return (h + 2, w + 2, mp, found)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bt % n for bt in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['YES', 'NO']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
ans = 0
(n, m) = LI()
(g, c) = GI(n, m)

def bfs(x):
	v = [0] * n
	q = [x]
	while q:
		c = q.pop()
		v[c] = 1
		for nb in g[c]:
			if v[nb] == 0:
				q.append(nb)
				v[nb] = 1
	return sum(v)
x = min(bfs(0), bfs(1))
print(n * (n - 1) // 2 - x * (n - x) - m)


class UnionFind:

	def __init__(self, numV):
		self.pars = list(range(numV))
		self.ranks = [0] * numV
		self.sizes = [1] * numV
		self.numEs = [0] * numV

	def find(self, x):
		if self.pars[x] == x:
			return x
		else:
			self.pars[x] = self.find(self.pars[x])
			return self.pars[x]

	def union(self, x, y):
		(x, y) = (self.find(x), self.find(y))
		if x == y:
			self.numEs[x] += 1
		elif self.ranks[x] < self.ranks[y]:
			self.pars[x] = y
			self.sizes[y] += self.sizes[x]
			self.numEs[y] += self.numEs[x] + 1
		else:
			self.pars[y] = x
			self.sizes[x] += self.sizes[y]
			self.numEs[x] += self.numEs[y] + 1
			if self.ranks[x] == self.ranks[y]:
				self.ranks[x] += 1

	def same(self, x, y):
		return self.find(x) == self.find(y)
(N, M) = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]
UF = UnionFind(N)
for (A, B) in ABs:
	UF.union(A - 1, B - 1)
for v in range(N):
	UF.find(v)
par1 = UF.find(0)
par2 = UF.find(1)
pars = set(UF.pars)
sizeOther = numEOther = 0
for par in pars:
	if par == par1:
		size1 = UF.sizes[par]
		numE1 = UF.numEs[par]
	elif par == par2:
		size2 = UF.sizes[par]
		numE2 = UF.numEs[par]
	else:
		sizeOther += UF.sizes[par]
		numEOther += UF.numEs[par]
size = size1 + sizeOther
numE = numE1 + numEOther
ans1 = size * (size - 1) // 2 - numE + size2 * (size2 - 1) // 2 - numE2
size = size2 + sizeOther
numE = numE2 + numEOther
ans2 = size * (size - 1) // 2 - numE + size1 * (size1 - 1) // 2 - numE1
print(max(ans1, ans2))


(n, m) = map(int, input().split())
a = [i for i in range(n + 1)]
b = [0] * (n + 1)

def f(x):
	if a[x] == x:
		return x
	x = a[x]
	return f(x)

def s(x, y):
	x = f(x)
	y = f(y)
	if x != y:
		if b[x] < b[y]:
			a[x] = y
			b[y] += 1
		else:
			a[y] = x
			b[x] += 1
for i in range(m):
	(c, d) = map(int, input().split())
	s(c, d)
for i in range(1, n + 1):
	a[i] = f(i)
d = a.count(a[2])
s = a.count(a[1])
print(max((n - d) * (n - d - 1) // 2 - m + d * (d - 1) // 2, (n - s) * (n - s - 1) // 2 - m + s * (s - 1) // 2))


def examA():
	bit = 41
	(N, K) = LI()
	A = LI()
	B = [0] * bit
	for a in A:
		for j in range(bit):
			if a & 1 << j > 0:
				B[j] += 1
	ans = 0
	cnt = 0
	for i in range(bit)[::-1]:
		if N - B[i] <= B[i]:
			ans += (1 << i) * B[i]
		elif cnt + (1 << i) > K:
			ans += (1 << i) * B[i]
		else:
			cnt += 1 << i
			ans += (1 << i) * (N - B[i])
	print(ans)
	return

def examB():
	(N, K) = LI()
	WP = [LI() for _ in range(N)]
	l = 0
	r = 101
	for _ in range(100):
		now = (l + r) / 2
		W = [0] * N
		for (i, (w, p)) in enumerate(WP):
			W[i] = w * (p - now)
		W.sort(reverse=True)
		if sum(W[:K]) >= 0:
			l = now
		else:
			r = now
	ans = l
	print(ans)
	return

def examC():

	class UnionFind:

		def __init__(self, n):
			self.parent = [-1 for _ in range(n)]

		def find(self, x):
			if self.parent[x] < 0:
				return x
			else:
				self.parent[x] = self.find(self.parent[x])
				return self.parent[x]

		def unite(self, x, y):
			(x, y) = (self.find(x), self.find(y))
			if x == y:
				return False
			else:
				if self.size(x) < self.size(y):
					(x, y) = (y, x)
				self.parent[x] += self.parent[y]
				self.parent[y] = x

		def same(self, x, y):
			return self.find(x) == self.find(y)

		def size(self, x):
			x = self.find(x)
			return -self.parent[x]

		def is_root(self, x):
			return self.parent[x] < 0

		def roots(self):
			return [i for (i, x) in enumerate(self.parent) if x < 0]

		def members(self, x):
			root = self.find(x)
			return [i for i in range(self.n) if self.find(i) == root]

		def group_count(self):
			return len(self.roots())

		def all_group_members(self):
			return {r: self.members(r) for r in self.roots()}
	(N, M) = LI()
	Uf = UnionFind(N)
	for _ in range(M):
		(a, b) = LI()
		a -= 1
		b -= 1
		Uf.unite(a, b)
	size = [Uf.size(0), Uf.size(1)]
	size.sort()
	rest = N - sum(size)
	size[1] += rest
	ans = size[0] * (size[0] - 1) // 2 + size[1] * (size[1] - 1) // 2 - M
	print(ans)
	return

def examD():
	ans = 0
	print(ans)
	return
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = 10 ** (-12)
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 7)
examC()


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			self.par[x] = y
		else:
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def ans(self):
		print(len(set(self.par)) - 1)
(n, m) = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
	(a, b) = map(int, input().split())
	uf.union(a, b)
a = 1
b = 1
c = 0
for i in range(3, n + 1):
	if uf.same_check(1, i):
		a += 1
	elif uf.same_check(2, i):
		b += 1
	else:
		c += 1
if a > b:
	a += c
else:
	b += c
print(a * (a - 1) // 2 + b * (b - 1) // 2 - m)


(N, M) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
used = [0] * N

def dfs(s):
	st = [s]
	used[s] = 1
	res = 0
	while st:
		s = st.pop()
		res += 1
		for t in G[s]:
			if not used[t]:
				used[t] = 1
				st.append(t)
	return res
g = min(dfs(0), dfs(1))
print(N * (N - 1) // 2 - g * (N - g) - M)


class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * (n + 1)

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
(N, M) = map(int, input().split())
graph = []
G = UnionFind(N)
for i in range(M):
	(a, b) = map(int, input().split())
	G.union(a, b)
A = G.size(1)
B = G.size(2)
C = N - A - B
ans = 0
for i in range(C + 1):
	ans = max(ans, (A + i) * (A + i - 1) // 2 + (B + C - i) * (B + C - i - 1) // 2 - M)
print(ans)


class UnionFind:

	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.node_size = [1] * n
		self.edge_size = [0] * n
		self.rank = [0] * n

	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]

	def same_check(self, x, y):
		return self.find(x) == self.find(y)

	def get_node_size(self, x):
		return self.node_size[self.find(x)]

	def get_edge_size(self, x):
		return self.edge_size[self.find(x)]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			self.edge_size[x] += 1
		elif self.rank[x] < self.rank[y]:
			self.par[x] = y
			self.edge_size[y] += self.edge_size[x] + 1
			self.node_size[y] += self.node_size[x]
		else:
			self.par[y] = x
			self.edge_size[x] += self.edge_size[y] + 1
			self.node_size[x] += self.node_size[y]
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
(n, m) = [int(item) for item in input().split()]
UF = UnionFind(n)
for i in range(m):
	(x, y) = [int(item) - 1 for item in input().split()]
	UF.union(x, y)
unconnected_node = 0
unconnected_edge = 0
seen = set()
p0 = UF.find(0)
p1 = UF.find(1)
for i in range(n):
	pi = UF.find(i)
	if pi != p0 and pi != p1:
		if pi not in seen:
			unconnected_edge += UF.edge_size[pi]
			unconnected_node += UF.node_size[pi]
			seen.add(pi)
if UF.get_node_size(0) > UF.get_node_size(1):
	large = 0
	small = 1
else:
	large = 1
	small = 0
A = UF.get_node_size(large) + unconnected_node
B = UF.get_node_size(small)
ans = A * (A - 1) // 2 + B * (B - 1) // 2
ans -= UF.get_edge_size(large) + UF.get_edge_size(small) + unconnected_edge
print(ans)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

class UnionFind(object):

	def __init__(self, N):
		self.parent = [-1] * N

	def root(self, A):
		if self.parent[A - 1] < 0:
			return A
		self.parent[A - 1] = self.root(self.parent[A - 1])
		return self.parent[A - 1]

	def size(self, A):
		return -1 * self.parent[self.root(A) - 1]

	def connect(self, A, B):
		A = self.root(A)
		B = self.root(B)
		if A == B:
			return False
		if self.size(A) < self.size(B):
			(A, B) = (B, A)
		self.parent[A - 1] += self.parent[B - 1]
		self.parent[B - 1] = A
		return True

	def same(self, A, B):
		if self.root(A) == self.root(B):
			return True
		else:
			return False
(N, M) = map(int, input().split())
uni = UnionFind(N)
for _ in range(M):
	(a, b) = map(int, input().split())
	uni.connect(a, b)
group1 = uni.size(1)
group2 = uni.size(2)
other = 0
for i in range(3, N + 1):
	if uni.same(1, i):
		continue
	if uni.same(2, i):
		continue
	other += 1
if group1 < group2:
	group2 += other
else:
	group1 += other
ans = group1 * (group1 - 1) // 2 + group2 * (group2 - 1) // 2 - M
print(ans)


class UnionFindTree:

	def __init__(self, N):
		self.N = N
		self.__parent_of = [None] * N
		self.__rank_of = [0] * N
		self.__size = [1] * N

	def root(self, value):
		if self.__parent_of[value] is None:
			return value
		else:
			self.__parent_of[value] = self.root(self.__parent_of[value])
			return self.__parent_of[value]

	def unite(self, a, b):
		r1 = self.root(a)
		r2 = self.root(b)
		if r1 != r2:
			if self.__rank_of[r1] < self.__rank_of[r2]:
				self.__parent_of[r1] = r2
				self.__size[r2] += self.__size[r1]
			else:
				self.__parent_of[r2] = r1
				self.__size[r1] += self.__size[r2]
				if self.__rank_of[r1] == self.__rank_of[r2]:
					self.__rank_of[r1] += 1

	def is_same(self, a, b):
		return self.root(a) == self.root(b)

	def size(self, a):
		return self.__size[self.root(a)]

	def groups(self):
		groups = {}
		for k in range(self.N):
			r = self.root(k)
			if r not in groups:
				groups[r] = []
			groups[r].append(k)
		return [groups[x] for x in groups]

def main():
	(N, M) = map(int, input().split())
	uft = UnionFindTree(N)
	for _ in range(M):
		(a, b) = map(int, input().split())
		uft.unite(a - 1, b - 1)
	ans = 0
	for g in uft.groups():
		if 0 in g or 1 in g:
			x = len(g)
			y = N - x
			ans = max(ans, x * (x - 1) // 2 + y * (y - 1) // 2 - M)
	print(ans)
main()


class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n
		self.links = [0] * n
		self.nodes = [1] * n

	def _root(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self._root(self.table[x])
			return self.table[x]

	def find(self, x, y):
		return self._root(x) == self._root(y)

	def union(self, x, y):
		r1 = self._root(x)
		r2 = self._root(y)
		if r1 == r2:
			self.links[r1] += 1
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			if d1 == d2:
				self.table[r1] -= 1
			self.links[r1] += self.links[r2] + 1
			self.nodes[r1] += self.nodes[r2]
			return
		else:
			self.table[r1] = r2
			self.links[r2] += self.links[r1] + 1
			self.nodes[r2] += self.nodes[r1]
			return
(n, m) = map(int, input().split())
uft = UnionFind(n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	uft.union(a, b)
(r1, r2) = (uft._root(0), uft._root(1))
for i in range(2, n):
	ri = uft._root(i)
	if r1 != ri and r2 != ri:
		uft.union(n, i)
rn = uft._root(n)
(l1, l2, ln) = (uft.links[r1], uft.links[r2], uft.links[rn])
(n1, n2) = (uft.nodes[r1], uft.nodes[r2])
others = n - n1 - n2
ln -= others
add1_1 = (n1 + others) * (n1 + others - 1) // 2 - l1 - ln
add1_2 = n2 * (n2 - 1) // 2 - l2
add2_1 = n1 * (n1 - 1) // 2 - l1
add2_2 = (n2 + others) * (n2 + others - 1) // 2 - l2 - ln
print(max(add1_1 + add1_2, add2_1 + add2_2))


import collections
(n, m) = [int(v) for v in input().split()]
connect_list = [[] for i in range(n)]
for i in range(m):
	(a, b) = [int(v) - 1 for v in input().split()]
	connect_list[a].append(b)
	connect_list[b].append(a)

def dfs(a):
	color = [0 for i in range(n)]
	color[a] = 1
	stack = collections.deque([a])
	r = 0
	while stack:
		s = stack.pop()
		color[s] = 2
		r += 1
		for i in connect_list[s]:
			if color[i] == 0:
				color[i] = 1
				stack.append(i)
	return r
(x, y) = (dfs(0), dfs(1))
(x, y) = (max(x, y), min(x, y))

def part_edge(a):
	return a * (a - 1) // 2
x = n - y
total_edge = part_edge(x) + part_edge(y)
print(total_edge - m)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

class UF_tree:

	def __init__(self, n):
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

	def find(self, x):
		if self.root[x] < 0:
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		elif self.rank[x] < self.rank[y]:
			self.root[y] += self.root[x]
			self.root[x] = y
		else:
			self.root[x] += self.root[y]
			self.root[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

	def size(self, x):
		return -self.root[self.find(x)]
(N, M) = map(int, input().split())
uf = UF_tree(N)
edge = [0] * (N + 1)
for _ in range(M):
	(a, b) = map(int, input().split())
	uf.unite(a, b)
	edge[a] += 1
	edge[b] += 1
x_root = uf.size(1)
y_root = uf.size(2)
if x_root < y_root:
	t = 2
else:
	t = 1
ans = 0
other = N - uf.size(1) - uf.size(2)
for x in range(1, N + 1):
	if uf.isSame(x, 1):
		if t == 2:
			other_v = 0
		else:
			other_v = other
		self_v = uf.size(1) - edge[x] - 1
		ans += other_v + self_v
	elif uf.isSame(x, 2):
		if t == 1:
			other_v = 0
		else:
			other_v = other
		self_v = uf.size(2) - edge[x] - 1
		ans += other_v + self_v
	else:
		root_v = uf.size(t)
		other_v = other - edge[x] - 1
		ans += other_v + root_v
print(ans // 2)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
P = [i for i in range(N + 1)]
size = [1 for i in range(N + 1)]

def find(a):
	if a == P[a]:
		return a
	else:
		return find(P[a])

def union(b, c):
	B = find(b)
	C = find(c)
	if P[B] < P[C]:
		P[C] = P[B]
	else:
		P[B] = P[C]
L = []
for i in range(M):
	(a, b) = map(int, input().split())
	L.append([a, b])
	union(a, b)
p = [i for i in range(N + 1)]
for i in range(1, N + 1):
	p[i] = find(i)
One = 0
Two = 0
Other = 0
for i in range(1, N + 1):
	if p[i] == 2:
		Two += 1
	elif p[i] == 1:
		One += 1
	else:
		Other += 1
if One > Two:
	One += Other
else:
	Two += Other
print(One * (One - 1) // 2 + Two * (Two - 1) // 2 - M)


def root(x):
	while p[x] >= 0:
		x = p[x]
	return x

def unite(a, b):
	(a, b) = (root(a), root(b))
	if a != b:
		if p[a] > p[b]:
			(a, b) = (b, a)
		p[a] += p[b]
		p[b] = a
(n, m, *t) = map(int, open(0).read().split())
p = [-1] * n
c = [0] * n
for (a, b) in zip(*[iter(t)] * 2):
	a -= 1
	b -= 1
	unite(a, b)
	c[a] += 1
	c[b] += 1
a = (root(0), root(1))
f = p[a[0]] < p[a[1]]
t = [0, 0]
for i in range(n):
	j = root(i)
	if j == a[f]:
		t[f] += c[i]
	else:
		t[f ^ 1] += c[i]
		unite(a[f ^ 1], j)
r = 0
for i in (0, 1):
	n = -p[root(i)]
	r += n * (n - 1) - t[i] >> 1
print(r)