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: Wrong Answer

Solution code:
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 #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    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] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-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):
    # print ('親', uni.root(i))
    if uni.root(i) > 2:
        other += 1

#片方に固めたほうが良い？
if group1 < group2:
    group2 += other
else:
    group1 += other

if group1 + group2 != N:
    print ('error')
# print (group1, group2)
ans = group1 * (group1 - 1) // 2 + group2 * (group2 - 1) // 2 - M
print (ans)
# print (uni.parent)

Submission status: Wrong Answer

Solution code:
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 #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    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] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-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):
    # print ('親', uni.root(i))
    if uni.root(i) > 2:
        other += 1

#片方に固めたほうが良い？
if group1 < group2:
    group2 += other
else:
    group1 += other

# print (group1, group2)
ans = group1 * (group1 - 1) // 2 + group2 * (group2 - 1) // 2 - M
print (ans)
# print (uni.parent)

Submission status: Wrong Answer

Solution code:
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 #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    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] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-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())
G = [0] * (N + 1)

uni = UnionFind(N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    G[a] += 1
    G[b] += 1
    uni.connect(a, b)

group1 = uni.size(1)
group2 = uni.size(2)

other = 0
for i in range(3, N + 1):
    # print ('親', uni.root(i))
    if uni.root(i) > 2:
        other += 1

if group1 < group2:
    group2 += other
else:
    group1 += other

# print (group1, group2)
ans = group1 * (group1 - 1) // 2 + group2 * (group2 - 1) // 2 - M
print (ans)

Submission status: Wrong Answer

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # 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.find(1)
    y_root = uf.find(2)
    if x_root < y_root:
        t = 1
    else:
        t = 2
    t_size = uf.size(t)

    ans = 0
    other = N - uf.size(1) - uf.size(2)  # 1とも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)

Submission status: Wrong Answer

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


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)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
size[1]=10**6
size[2]=10**6
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 size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
    union(a,b)


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)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
size[1]=10**6
size[2]=10**6
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 size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
    union(a,b)


One=0
Two=0
for i in range(1,N+1):
    if P[i]==2:
        Two+=1
    elif P[i]==1:
        One+=1
if One>Two:
    One=N-Two
else:
    Two=N-One

print(One*(One-1)//2+Two*(Two-1)//2- M)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
size[2]=10**6
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 size[C]>size[B]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([a,b])
    union(a,b)
    
#print(P)

One=0
Two=0
for i in range(1,N+1):
    if P[i]==2:
        Two+=1
    else:
        One+=1
#print(Two,One)
OneP=0
TwoP=0
for i in range(M):
    if P[L[i][0]]==2:
        TwoP+=1
    else:
        OneP+=1
#print(TwoP,OneP)
print(One*(One-1)//2+Two*(Two-1)//2- OneP - TwoP)

Submission status: Wrong Answer

Solution code:
n, m= map(int , input().strip().split(' '))
print((n-1) * (m - 1))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,raw_input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

a = b = 0
visited = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  visited[fr] = 1
  a += 1
  for to in es[fr]:
    if visited[to] > 0: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  visited[fr] = 1
  b += 1
  for to in es[fr]:
    if visited[to] > 0: continue
    stack.append(to)

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: Time Limit Exceeded

Solution code:
N,M = map(int,raw_input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

a = b = 0
visited = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    a += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  if not visited[fr]:
    visited[fr] = 1
    b += 1
  for to in es[fr]:
    if visited[to]: continue
    stack.append(to)

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: Time Limit Exceeded

Solution code:
from collections import Counter
N,M = map(int,raw_input().split())

es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

group = [0 for i in range(N)]
stack = [0]
while stack:
  fr = stack.pop()
  group[fr] = 1
  for to in es[fr]:
    if group[to] > 0: continue
    stack.append(to)

stack = [1]
while stack:
  fr = stack.pop()
  group[fr] = 2
  for to in es[fr]:
    if group[to] > 0: continue
    stack.append(to)

ctr = Counter(group)
a = ctr[1]
b = ctr[2]
if a > b: a,b = b,a
b += ctr[0]

ans = a*(a-1)//2 + b*(b-1)//2 - M
print(ans)

Submission status: Accepted

Solution code:
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 #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    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] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-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):
    # print ('親', uni.root(i))
    if (uni.same(1, i)):
        continue
    if (uni.same(2, i)):
        continue
    other += 1

#片方に固めたほうが良い？
if group1 < group2:
    group2 += other
else:
    group1 += other

# print (group1, group2)
ans = group1 * (group1 - 1) // 2 + group2 * (group2 - 1) // 2 - M
print (ans)
# print (uni.parent)

Submission status: Accepted

Solution code:
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):
            # 要素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が属するグループとを併合する
            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):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素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):
            # 要素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
"""

Submission status: Accepted

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # 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)  # 1とも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)

Submission status: Accepted

Solution code:
# Atcoder Problem Solving
# Shock

# Code Fesitival Team Relay


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)

Submission status: Accepted

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

Submission status: Accepted

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=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: Accepted

Solution code:
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}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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()
#sys.setrecursionlimit(10**7)
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)

Submission status: Accepted

Solution code:
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}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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()
#sys.setrecursionlimit(10**7)
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: # i belongs to x
        ans+=nx-1-len(g[i])
    else:
        ans+=ny-1-len(g[i])

print(ans//2)

Submission status: Accepted

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