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):
from collections import defaultdict


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


N,M,K=list(map(int,input().split()))
group=UnionFind(N)
friend=defaultdict(int)
for _ in range(M):
    src,dst=list(map(int,input().split()))
    group.Unite(src-1,dst-1)
    friend[src-1]+=1
    friend[dst-1]+=1

block=defaultdict(list)
for _ in range(K):
    src,dst=list(map(int,input().split()))
    block[src-1].append(dst-1)
    block[dst-1].append(src-1)

ans=[]
for i in range(N):
    total=group.Count(i)
    num=total-1-friend[i]
    
    for b in block[i]:
        if group.isSameGroup(i,b):
            num-=1
    ans.append(num)

for i in ans:
    print(i,end=" ")
print()

Solution (Python):
N, M, K = map(int, input().split())


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)

edge1 = []
edge2 = []

for _ in range(M):
    a, b = map(int, input().split())
    edge1.append((a - 1, b - 1))

for _ in range(K):
    a, b = map(int, input().split())
    edge2.append((a - 1, b - 1))

for a, b in edge1:
    uf.union(a, b)

res = [uf.size(i) - 1 for i in range(0, N)]

for a, b in edge1:
    res[a] -= 1
    res[b] -= 1

for a, b in edge2:
    if uf.same(a, b):
        res[a] -= 1
        res[b] -= 1

print(' '.join(map(str, res)))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

N, M, K = map(int, input().split())
uf = UnionFind(N)

fre = [set() for i in range(N)]

for i in range(M):
  a, b = map(int, input().split())
  fre[a-1].add(b-1)
  fre[b-1].add(a-1)
  uf.unite(a-1, b-1)

ble = [tuple(map(int, input().split())) for i in range(K)]

ans = [0] * N
t = {}
for n in range(N):
  t[uf.root(n)] = t.get(uf.root(n), 0) + 1

for n in range(N):
  ans[n] = t[uf.root(n)] - len(fre[n]) - 1

for a, b in ble:
  if uf.same(a-1, b-1):
    ans[a-1] -= 1
    ans[b-1] -= 1

print(*ans)

Solution (Python):
import sys
from itertools import accumulate
n, m, k = [int(i) for i in sys.stdin.readline().split()]

par = list(range(n))
ns = [1 for i in range(n)]

def find(x):
    ls = []
    while x != par[x]:
        ls.append(x)
        x = par[x]
    for l in ls:
        par[l] = x
    return x

def unite(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y
        ns[y] += ns[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

ls = [0 for i in range(n)]
friends = [0 for i in range(n-1)]

for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    ls[a] -= 1
    ls[b] -= 1
    unite(a, b)

for i in range(n):
    root = find(i)
    ls[i] += ns[root]


for i in range(k):
    c, d = [int(i) for i in sys.stdin.readline().split()]
    c -= 1
    d -= 1
    if is_same(c, d):
        ls[c] -= 1
        ls[d] -= 1

print(" ".join([str(i - 1) for i in ls]))

Solution (Python):
from collections import defaultdict
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())
    fd = defaultdict(list)
    uf = UnionFind(N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        if a in fd:
            fd[a].append(b)
        else:
            fd[a] = [b]
        if b in fd:
            fd[b].append(a)
        else:
            fd[b] = [a]
        uf.union(a,b)
    for _ in range(K):
        c, d = map(int, input().split())
        if uf.same(c, d):
            fd[c].append(d)
            fd[d].append(c)
    r = []
    for i in range(1, N+1):
        r.append(uf.size(i)-len(fd[i])-1)
    print(' '.join(str(i) for i in r))
main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, m, k = LI()
    ab = LIR_(m)
    cd = LIR_(k)
    par = [i for i in range(n)]
    size = [1] * n
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(a, b):
        a = root(a)
        b = root(b)
        if size[a] > size[b]: a, b = b, a
        if a == b: return False
        par[a] = b
        size[b] += size[a]
        return True

    lis = [1] * n
    for a, b in ab:
        unite(a, b)
        lis[a] += 1
        lis[b] += 1
    for c, d in cd:
        if root(c) == root(d):
            lis[c] += 1
            lis[d] += 1
    for i in range(n):
        print(size[root(i)] - lis[i], end=" ")
    print()
    return



if __name__ == '__main__':
    solve()

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def ufinit(n):
  global ufsz, ufances
  ufsz = [1] * n
  ufances = [0] * n
  for i in range(n):
    ufances[i] = i

def ufroot(x):
  global ufances
  a = []
  y = x
  while ufances[y] != y:
    a.append(y)
    y = ufances[y]
  for z in a:
    ufances[z] = y
  return y

def ufconn(x,y):
  global ufsz, ufances
  i = ufroot(x)
  j = ufroot(y)
  if i==j:
    return
  
  k  = j if (ufsz[i]<ufsz[j]) else i
  if k==j:
    ufances[i] = j
  else:
    ufances[j] = i
  ufsz[k] = ufsz[i] + ufsz[j]

n,m,k = inm()
ufinit(n+1)
friend = [{} for i in range(n+1)]
for i in range(m):
    a,b = inm()
    friend[a][b] = 1
    friend[b][a] = 1
    ufconn(a,b)
blk = [{} for i in range(n+1)]
for i in range(k):
    a,b = inm()
    blk[a][b] = 1
    blk[b][a] = 1
gr = {}
for i in range(1,n+1):
    r = ufroot(i)
    if r in gr:
        gr[r] += 1
    else:
        gr[r] = 1
for i in range(1,n+1):
    r = ufroot(i)
    x = gr[r]-1
    for f in friend[i]:
        if ufroot(f)==r:
            x -= 1
    for f in blk[i]:
        if ufroot(f)==r:
            x -= 1
    printn(str(x)+' ')
print("")

Solution (Python):
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx 

N, M, K = lr()
AB = [lr() for _ in range(M)]
friends = [[] for _ in range(N+1)]
block = [set() for _ in range(N+1)]
for a, b in AB:
    friends[a].append(b)
    friends[b].append(a)

for _ in range(K):
    c, d = lr()
    block[c].add(d)
    block[d].add(c)

V = [i for i in range(N+1)] 
for a, b in AB:
    if find(V, a) != find(V, b):
        union(V, a, b)

for i in range(1, N+1):
    V[i] = find(V, i)

for i in range(1, N+1):
    rmv = set()
    for x in block[i]:
        if V[i] != V[x]:
            rmv.add(x)
    block[i] -= rmv

counter = Counter(V)

answer = [None] * (N+1)
for i in range(1, N+1):
    num = counter[V[i]]
    answer[i] = num - len(friends[i]) - len(block[i]) - 1

print(*answer[1:])

Solution (Python):
import sys
input=sys.stdin.readline
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)] 
        self.rank=[0]*n 
        self.size=[1]*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 union(self,x,y):
        px=self.find(x)
        py=self.find(y)
        if px!=py:
            if self.rank[px]==self.rank[py]: 
                self.rank[px]+=1
            elif self.rank[px]<self.rank[py]:
                px,py=py,px 
            self.par[py]=px 
            self.size[px]+=self.size[py]
    def same_check(self,x,y): 
        return self.find(x)==self.find(y)
    
def main():
    n,m,k=map(int,input().split())
    uf=UnionFind(n)
    F_edges=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1
        uf.union(a,b)
        F_edges[a].append(b)
        F_edges[b].append(a)
    B=[0]*n
    for _ in range(k):
        a,b=map(int,input().split())
        a-=1; b-=1
        if uf.same_check(a,b):
            B[a]+=1
            B[b]+=1
    Ans=[]
    for i in range(n):
        Ans.append(uf.size[uf.find(i)]-1-len(F_edges[i])-B[i])
    print(*Ans)
    
if __name__=='__main__':
    main()

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

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

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

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

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

n, m, k = map(int, input().split())
U = UnionFind(n)
may_friend = [-1 for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    U.union(a, b)
    may_friend[a] += -1
    may_friend[b] += -1
for i in range(k):
    c, d = map(int, input().split())
    if U.check(c, d):
        may_friend[c] += -1
        may_friend[d] += -1

ans = [max(0, may_friend[i] + U.size(i)) for i in range(1, n + 1)]
print(*ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(500000)










    








    











        


    


    







class UnionFind:
    def __init__(self,N):
        self.root = list(range(N+1))
        self.size = [1] * (N+1)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy

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


if __name__ == "__main__":

    N,M,K = map(int, readline().split())
    A = [0] * (M+5)
    B = [0] * (M+5)
    C = [0] * (K+5)
    D = [0] * (K+5)
    for i in range(M):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        A[i] = a 
        B[i] = b 
    for i in range(K):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        C[i] = a 
        D[i] = b 
    uf = UnionFind(N)
    for i in range(M):
        uf.merge(A[i], B[i])

    arr = [[] for _ in range(N+2)]
    edge = [[] for _ in range(N+2)]
    for i in range(N):
        arr[uf.find_root(i)].append(i)
    
    for i in range(M):
        if uf.find_root(A[i]) == uf.find_root(B[i]):
            edge[uf.find_root(A[i])].append(i)
    
    for i in range(K):
        if uf.find_root(C[i]) == uf.find_root(D[i]):
            edge[uf.find_root(C[i])].append(i + M)
        

    ans = ["0"] * N
    for i in range(N):
        dd = {}
        if len(arr[i]) == 0:
            continue
        sz = uf.sz(i)
        for j, v in enumerate(arr[i]):
            dd[v] = j
        friends = [0] * (sz+2)
        for e in edge[i]:
            if e <= M-1:
                friends[dd[A[e]]] += 1
                friends[dd[B[e]]] += 1
            else:
                friends[dd[C[e-M]]] += 1
                friends[dd[D[e-M]]] += 1
        for v in arr[i]:
            res = sz - friends[dd[v]] - 1
            ans[v] = str(res)
    print(" ".join(ans))

Solution (Python):

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 is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

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


N, M, K = map(int, input().split())
friend = [list(map(int, input().split())) for _ in range(M)]
block = [list(map(int, input().split())) for _ in range(K)]

friend_count = [0] * (N + 1)
block_with = [[] for _ in range(N + 1)]
uf = UnionFind(N + 1)

for f in friend:
    friend_count[f[0]] += 1
    friend_count[f[1]] += 1
    uf.unite(f[0], f[1])

for b in block:
    block_with[b[0]].append(b[1])
    block_with[b[1]].append(b[0])

for i in range(1, N + 1):
    ans = uf.count(i) - friend_count[i] - 1
    for b in block_with[i]:
        if uf.is_same_group(i, b):
            ans -= 1
    if i > 1:
        print(" ", end="")
    print(ans, end="")

print()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = 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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

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


import sys
input = sys.stdin.buffer.readline

n, m, k = map(int, input().split())
friend = UnionFind(n)
f_cnt = [0] * n
for _ in range(m):
	a, b = map(int, input().split())
	a -= 1
	b -= 1
	friend.unite(a, b)
	f_cnt[a] += 1
	f_cnt[b] += 1
block = [[] for _ in range(n)]
for _ in range(k):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
ans = []
for i in range(n):
	ret = friend.size(i) - f_cnt[i] - 1
	for j in block[i]:
		if friend.isSame(i, j):
			ret -= 1
	ans.append(ret)
print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)


class Tree:
    WHITE = -2
    GRAY = -1
    BLACK = 1

    def __init__(self, adj):
        n = len(adj)
        self.adj = adj
        self.colors = [self.WHITE] * n
        self.depths = [-1] * n
        self.depth = 0

    def init(self):
        self.__init__(self.adj)

    def dfs(self, u, c):
        if self.colors[u] >= 0:
            return

        self.colors[u] = self.GRAY
        self.depths[u] = self.depth

        for v in self.adj[u]:
            if self.colors[v] == self.WHITE:
                self.dfs(v, c)

        self.colors[u] = c

from collections import Counter

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

tree = Tree(adj)
for i in range(n):
    tree.dfs(i, i)

labels = tree.colors

counter = Counter(labels)

ans = [counter[labels[i]] - 1 for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    c -= 1
    d -= 1
    if labels[c] == labels[d]:
        ans[c] -= 1
        ans[d] -= 1

print(*ans)

Solution (Python):
from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]
        self.sz = defaultdict(lambda:1)

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            size = self.sz[s1]+self.sz[s2]
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            s = self.find(x)
            self.sz[s] = size
            return True
        return False

    def size(self, x):
        s = self.find(x)
        return self.sz[s]
N,M,K = map(int,input().split())
u = UnionFind(N)
friend = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)
    u.union(A-1,B-1)
block = [[] for _ in range(N)]
for i in range(K):
    C,D = map(int,input().split())
    block[C-1].append(D-1)
    block[D-1].append(C-1)
ans = [0]*N
for i in range(N):
    ans[i] = u.size(i)-1
    for f in friend[i]:
        if u.find(i)==u.find(f):
            ans[i] -= 1
    for b in block[i]:
        if u.find(i)==u.find(b):
            ans[i] -= 1
print(*ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
INF = float("inf")
from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))  


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    
    block = Graph(N)
    for c, d in zip(C, D):
        block.add_edge(c-1, d-1)

    
    friendUF = UnionFind(N)
    degree = [0]*N
    for a, b in zip(A, B):
        friendUF.unite(a-1, b-1)
        degree[a-1] += 1
        degree[b-1] += 1

    
    group = defaultdict(int)
    for i in range(N):
        group[friendUF.root(i)] += 1

    ans = []
    for i in range(N):
        
        
        
        ans.append(group[friendUF.root(i)] - degree[i] - 1)
        
        for dest, _ in block.E[i]:
            if friendUF.same(dest, i):
                ans[-1] -= 1
    print(*ans, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  
    D = [int()] * (K)  
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)


if __name__ == '__main__':
    main()

Solution (Python):
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)]
N,M,K = map(int,input().split())
C = UnionFind(N)
F = [0]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    C.Unite(a,b)
    F[a]+=1
    F[b]+=1
B = [[] for i in range(N+1)]
for h in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
A = [0]*N
for n in range(1,N+1):
    all_ = C.Count(n)
    B_cnt = 0
    for b in B[n]:
        if C.isSameGroup(n,b):B_cnt+=1
    A[n-1] = all_ - B_cnt - F[n] - 1
print(*A)

Solution (Python):
from collections import Counter

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 = list(map(int,input().split()))
    counter = Counter()
    uf = UnionFind(N+1)
    for i in range(M):
        a,b = list(map(int,input().split()))
        counter.update((a,b))
        uf.union(a,b)
    
    ans = [0]*(N+1)

    for i in range(1,N+1):
        ans[i] = uf.size(i)-counter[i]-1
    for i in range(K):
        a,b = list(map(int,input().split()))
        if uf.same(a,b):
            ans[a] -= 1
            ans[b] -= 1
    
    for i in range(1,N):
        print(ans[i] if 0<=ans[i] else 0,end=" ")
    print(ans[N] if 0<=ans[i] else 0)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = 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 unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return 0
		elif self.rank[x] > self.rank[y]:
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

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

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

import sys
input=sys.stdin.buffer.readline

n,m,k=map(int,input().split())
friend=UnionFind(n)
f_cnt=[0]*n
for _ in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	friend.unite(a,b)
	f_cnt[a]+=1
	f_cnt[b]+=1
block=[[] for _ in range(n)]
for _ in range(k):
	c,d=map(int,input().split())
	block[c-1].append(d-1)
	block[d-1].append(c-1)
ans=[]
for i in range(n):
	ret=friend.size(i)-f_cnt[i]-1
	for j in block[i]:
		if friend.isSame(i,j):
			ret-=1
	ans.append(ret)
print(*ans)