Problem:
 Score : 100 points    Problem Statement 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.        Sample Input 1 4 1
1 3      Sample Output 1 2   As shown above, two edges can be added. It is not possible to add three or more edges.       Sample Input 2 2 0      Sample Output 2 0   No edge can be added.       Sample Input 3 9 6
1 4
1 8
2 5
3 6
4 8
5 7      Sample Output 3 12

Solution (Python):
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)

Solution (Python):
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]
        else:
            if 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)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
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)]


if __name__ == "__main__":
    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)

Solution (Python):






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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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={'

    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)

Solution (Python):
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={'

    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),v

x,cx=bfs(0)
y,cy=bfs(1)
if x<y:
    cy=[1 if cx[i]==0 else 0 for i in range(n)]
    nx,ny=x,n-x
else:
    cx=[1 if cy[i]==0 else 0 for i in range(n)]
    nx,ny=n-y,y
for i in range(n):
    if cx[i]==1: 
        ans+=nx-1-len(g[i])
    else:
        ans+=ny-1-len(g[i])

print(ans//2)

Solution (Python):
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)

Solution (Python):
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)


if __name__ == "__main__":
    main()

Solution (Python):
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
        else:
            if 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)

Solution (Python):
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)

Solution (Python):
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)))

Solution (Python):
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)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)



from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import numpy as np

N,M = map(int,input().split())
A,B = np.array([input().split() for _ in range(M)], dtype=np.int32).reshape(M,2).T

graph = csr_matrix((np.ones(M),(A,B)), (N+1,N+1))

_,comp = connected_components(graph)

comp_size = np.bincount(comp[1:])

x1 = comp_size[comp[1]]
x2 = comp_size[comp[2]]
small = min(x1,x2)

answer = sum(x*(x-1)//2 for x in [small,N-small])
answer -= M
print(answer)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)