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



Sample input:
4 1
1 3


Sample output:
2

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
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,c=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)

Submission status: Runtime Error

Solution code:
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_sizes[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)

Submission status: Runtime Error

Solution code:
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_sizes[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()
for i in range(n):
    if not UF.same_check(0, i) and not UF.same_check(1, i):
        group = UF.find(i)
        if group not in seen:
            unconnected_edge += UF.edge_size[group]
            unconnected_node += UF.node_size[group]
            seen.add(group)

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)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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_sizes[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()
for i in range(n):
    if not UF.same_check(0, i) and not UF.same_check(1, i):
        group = UF.find(i)
        if group not in seen:
            unconnected_edge += UF.edge_size[group]
            unconnected_node += UF.node_size[group]
            seen.add(group)

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)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

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_sizes[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()
for i in range(n):
    if not UF.same_check(0, i) and not UF.same_check(1, i):
        group = UF.find(i)
        if group not in seen:
            unconnected_edge += UF.edge_size[group]
            unconnected_node += UF.node_size[group]
            seen.add(group)

if UF.node_size[0] > UF.node_size[1]:
    large = 0
    small = 1
else:
    large = 1
    small = 0

A = UF.node_size[large] + unconnected_node
B = UF.node_size[small]
ans = A * (A - 1) // 2 + B * (B - 1) // 2
ans -= UF.edge_size[large] + UF.edge_size[small] + unconnected_edge
print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
from collections import Counter
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[y]=x
            b[y]+=1
        else:
            a[x]=y
            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])
print(((n-d)*(n-d-1)//2)-m+(d*(d-1)//2))

Submission status: Runtime Error

Solution code:
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):
    used[s] = 1
    res = 1
    for t in G[s]:
        if not used[t]:
            res += dfs(t)
    return res
g = min(dfs(0), dfs(1))
print(N*(N-1)//2 - g*(N - g) - M)