Problem:
 Score : 400 points    Problem Statement An SNS has N users - User 1 , User 2 , \cdots , User N .  Between these N users, there are some relationships - M  friendships and K  blockships .  For each i = 1, 2, \cdots, M , there is a bidirectional friendship between User A_i and User B_i .  For each i = 1, 2, \cdots, K , there is a bidirectional blockship between User C_i and User D_i .  We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:   a \neq b .  There is not a friendship between User a and User b .  There is not a blockship between User a and User b .  There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a , c_L = b , and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1 .   For each user i = 1, 2, ... N , how many friend candidates does it have?      Constraints  All values in input are integers.  2 ≤ N ≤ 10^5  0 \leq M \leq 10^5  0 \leq K \leq 10^5  1 \leq A_i, B_i \leq N  A_i \neq B_i  1 \leq C_i, D_i \leq N  C_i \neq D_i  (A_i, B_i) \neq (A_j, B_j) (i \neq j)  (A_i, B_i) \neq (B_j, A_j)  (C_i, D_i) \neq (C_j, D_j) (i \neq j)  (C_i, D_i) \neq (D_j, C_j)  (A_i, B_i) \neq (C_j, D_j)  (A_i, B_i) \neq (D_j, C_j)         Input Input is given from Standard Input in the following format:  N  M  K  A_1  B_1  \vdots  A_M  B_M  C_1  D_1  \vdots  C_K  D_K       Output Print the answers in order, with space in between.        Sample Input 1 4 4 1
2 1
1 3
3 2
3 4
4 1      Sample Output 1 0 1 0 1  There is a friendship between User 2 and 3 , and between 3 and 4 . Also, there is no friendship or blockship between User 2 and 4 . Thus, User 4 is a friend candidate for User 2 .  However, neither User 1 or 3 is a friend candidate for User 2 , so User 2 has one friend candidate.       Sample Input 2 5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5      Sample Output 2 0 0 0 0 0  Everyone is a friend of everyone else and has no friend candidate.       Sample Input 3 10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1      Sample Output 3 1 3 5 4 3 3 3 3 1 0

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines





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

    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())


def main():
	n,m,k=map(int,input().split())
	u=UnionFind(n)
	f=[-1]*n
	for i in range(m):
		a,b=map(int,input().split())
		u.union(a-1,b-1)
		f[a-1]-=1
		f[b-1]-=1
	
	for i in range(k):
		a, b = map(int, input().split())
		if u.same(a-1,b-1):
			f[a - 1] -= 1
			f[b - 1] -= 1
	
	for i in range(n):
		f[i]+=u.size(i)
	
	print(*f)
	
	

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())




def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]



par = [-1]*n

num = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    num[a-1] += 1
    num[b-1] += 1

edge = [[] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    edge[c-1].append(d-1)
    edge[d-1].append(c-1)


for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e,i):
            cnt -= 1
    print(cnt,end=' ')

Solution (Python):
import sys
from io import StringIO
import unittest

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

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

def resolve():
    n,m,k=list(map(int,input().strip().split()))

    uf = UnionFind(n)

    res=[[] for i in range(n)]
    frd=[[] for i in range(n)]
    blk=[[] for i in range(n)]

    for i in range(m):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        uf.Unite(a,b)
        frd[a].append(b)
        frd[b].append(a)
    
    for i in range(k):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        
        
        frd[a].append(b)
        frd[b].append(a)
    
    rescnt=[]

    for i in range(n):
        ri=uf.Count(i)-1
        for f in frd[i]:
            if uf.isSameGroup(f,i):
                ri-=1
        rescnt.append(str(ri))
        
    
    print(" ".join(rescnt))

resolve()

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 4 1
2 1
1 3
3 2
3 4
4 1"""
        output = """0 1 0 1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5"""
        output = """0 0 0 0 0"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1"""
        output = """1 3 5 4 3 3 3 3 1 0"""
        self.assertIO(input, output)

if __name__ == "__main__":
    unittest.main()

Solution (Python):
from collections import defaultdict


def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def same(x, y):
    return find_root(x) == find_root(y)


def group_size(x):
    return size[find_root(x)]


dic1 = defaultdict(list)
dic2 = defaultdict(list)

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]


parent = [i for i in range(n)]  
rank = [1] * n  
size = [1] * n  

edge = [[ab[m - 1 - i][0] - 1, ab[m - 1 - i][1] - 1] for i in range(m)]

for i in range(m):
    a = find_root(edge[i][0])
    b = find_root(edge[i][1])
    if a != b:
        unite(a, b)


for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    dic1[a].append(b)
    dic1[b].append(a)
for i in range(k):
    c = cd[i][0] - 1
    d = cd[i][1] - 1
    if same(c, d):
        dic2[c].append(d)
        dic2[d].append(c)

ans = []
for i in range(n):
    ans.append(group_size(i)-1 - len(dic1[i]) - len(dic2[i]))
print(' '.join(map(str, ans)))

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

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        
            
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self,x,y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
ans = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ans[a] -= 1
    ans[b] -= 1
    u.union(a,b)

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*[u.size(i)+x for i,x in enumerate(ans)])

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, K, *ABCD = map(int, open(0).read().split())
AB, CD = ABCD[:2 * M], ABCD[2 * M:]

E = [[] for _ in range(N + 1)]
uf = UnionFind(N + 1)
for a, b in zip(*[iter(AB)] * 2):
    uf.union(a, b)
    E[a].append(b)
    E[b].append(a)

B = [[] for _ in range(N + 1)]
for c, d in zip(*[iter(CD)] * 2):
    B[c].append(d)
    B[d].append(c)

A = []
for i in range(1, N + 1):
    A.append(uf.size(i) - 1 - len(E[i]) - sum(1 for b in B[i] if uf.same(b, i)))

print(*A)

Solution (Python):
import sys
input = sys.stdin.readline

n,m,k= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
c= [list(map(int, input().split())) for i in range(k)]


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

    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())

uf=UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)

ans=[uf.size(i)-1 for i in range(n)]
for i in range(m):
    ans[a[i][0]-1]-=1
    ans[a[i][1]-1]-=1

for i in range(k):
    if uf.same(c[i][0]-1,c[i][1]-1):
        ans[c[i][0]-1]-=1
        ans[c[i][1]-1]-=1

print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.count = [1] * (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):
        if UnionFind.same_check(self,x,y):
            return
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
ans = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ans[a] -= 1
    ans[b] -= 1
    u.union(a,b)

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*[u.size(i)+x for i,x in enumerate(ans)])

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    def find(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

    def size(self,x):
        return -self.par[self.find(x)]
    def same(self,x,y):
        return self.find(x)==self.find(y)

N,M,K=map(int,input().split(' '))
Friend = UnionFind(N)
pull = [-1] * N
for i in range(M):
    a,b = map(int,input().split(' '))
    Friend.unite(a-1,b-1)
    pull[a-1] -= 1
    pull[b-1] -= 1
for i in range(K):
    c,d=map(int,input().split(' '))
    if Friend.same(c-1,d-1):
        pull[c-1] -=1
        pull[d-1] -=1
print(' '.join([str(Friend.size(i)+pull[i]) for i in range(N)]))

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

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        for y in data:
            self.par[y] = root
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self,x,y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
ans = [-1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ans[a] -= 1
    ans[b] -= 1
    u.union(a,b)

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*[u.size(i)+x for i,x in enumerate(ans)])

Solution (Python):
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())




def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]



par = [-1]*n

num = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    unite(a-1,b-1)
    num[a-1] += 1
    num[b-1] += 1

edge = [[] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    edge[c-1].append(d-1)
    edge[d-1].append(c-1)


for i in range(n):
    cnt = size(i) - num[i] - 1
    for e in edge[i]:
        if same(e,i):
            cnt -= 1
    print(cnt,end=' ')

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

    
    def find(self, x):
        
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                
                data.append(now)
                queue.append(self.par[now])
        
        for y in data:
            self.par[y] = root
        return root

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self,x,y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t


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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]

n,m,k = map(int,input().split())
u = UnionFind(n)
friend = [1 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    friend[a] += 1
    friend[b] += 1
    u.union(a,b)


ans = [u.size(i)-friend[i] for i in range(n)]

for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if u.same_check(c,d):
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Solution (Python):
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

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

    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())

uf_friend = UnionFind(N)
uf_block = UnionFind(N)

es_friend = [0 for _ in range(N)]
es_block = [0 for _ in range(N)]

for i in range(M):
    uf_friend.union(AB[i][0]-1, AB[i][1]-1)
    es_friend[AB[i][0]-1] += 1
    es_friend[AB[i][1]-1] += 1
for i in range(K):
    uf_block.union(CD[i][0]-1, CD[i][1]-1)
for i in range(K):
    if uf_friend.same(CD[i][0]-1, CD[i][1]-1):
        es_block[CD[i][0]-1] += 1
        es_block[CD[i][1]-1] += 1


ans = [0 for _ in range(N)]
for i in range(N):
    ans[i] = uf_friend.size(i) - es_friend[i] - es_block[i] - 1

print(" ".join(list(map(str, ans))))

Solution (Python):
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())

class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

cf=[[] for i in range(n)]
cb=[[] for i in range(n)]

UFa=UF(n)
for i in range(m):
  x,y=map(int,input().split())
  UFa.unite(x-1,y-1)
  cf[x-1].append(y-1)
  cf[y-1].append(x-1)
UFa.groupnum()

for i in range(k):
  x,y=map(int,input().split())
  cb[x-1].append(y-1)
  cb[y-1].append(x-1)

ans=[]
for i in range(n):
  x=(UFa.size(i)-1)-len(cf[i])
  for j in range(len(cb[i])):
    if UFa.samegroup(i,cb[i][j]):
      x-=1
  ans.append(str(x))
print(' '.join(ans))

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.buffer.readline

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

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return x

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    N, M, K = map(int, input().split())
    UF = UnionFind(N+1)
    fr_num = [0] * (N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        UF.unite(a, b)
        fr_num[a] += 1
        fr_num[b] += 1

    ans = [0] * (N+1)
    for i in range(1, N+1):
        ans[i] = UF.size(i) - 1 - fr_num[i]

    for _ in range(K):
        c, d = map(int, input().split())
        if UF.isSameGroup(c, d):
            ans[c] -= 1
            ans[d] -= 1
    print(*ans[1:])


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    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, K = map(int, input().split())
G = UnionFind(N)

friends = {i:0 for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    friends[a-1] += 1
    friends[b-1] += 1
    G.union(a-1, b-1)


for i in range(K):
    c, d = map(int, input().split())
    if G.same(c-1, d-1):
        friends[c-1] += 1
        friends[d-1] += 1

for i in range(N):
    print(G.size(i) - friends[i] - 1, end=' ')

Solution (Python):
import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())

class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

cf=[[] for i in range(n)]
cb=[[] for i in range(n)]

UFa=UF(n)
UFb=UF(n)
for i in range(m):
  x,y=map(int,input().split())
  UFa.unite(x-1,y-1)
  UFb.unite(x-1,y-1)
  cf[x-1].append(y-1)
  cf[y-1].append(x-1)
UFa.groupnum()

for i in range(k):
  x,y=map(int,input().split())
  cb[x-1].append(y-1)
  cb[y-1].append(x-1)

ans=[]
for i in range(n):
  x=(UFa.size(i)-1)-len(cf[i])
  for j in range(len(cb[i])):
    if UFa.samegroup(i,cb[i][j]):
      x-=1
  ans.append(str(x))
print(' '.join(ans))

Solution (Python):
from collections import defaultdict


def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])



def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def same(x, y):
    return find_root(x) == find_root(y)


def group_size(x):
    return size[find_root(x)]


dic1 = defaultdict(list)
dic2 = defaultdict(list)

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]


parent = [i for i in range(n)]  
rank = [1] * n  
size = [1] * n  

edge = [[ab[m - 1 - i][0] - 1, ab[m - 1 - i][1] - 1] for i in range(m)]

res = []
for i in range(m):
    a = find_root(edge[i][0])
    b = find_root(edge[i][1])
    if a == b:
        res.append(0)
    else:
        res.append(size[a] * size[b])
        unite(a, b)


for i in range(m):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    dic1[a].append(b)
    dic1[b].append(a)
for i in range(k):
    c = cd[i][0] - 1
    d = cd[i][1] - 1
    if same(c, d):
        dic2[c].append(d)
        dic2[d].append(c)

ans = []
for i in range(n):
    ans.append(group_size(i)-1 - len(dic1[i]) - len(dic2[i]))
print(' '.join(map(str, ans)))

Solution (Python):
from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)