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 sys import setrecursionlimit
setrecursionlimit(1 << 30)

nv, ne, nBad = map(int, input().split())
g = [[] for _ in range(nv)]
for _ in range(ne):
    u, v = map(lambda x: int(x) - 1, input().split())
    g[u].append(v)
    g[v].append(u)
a = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(nBad)]

def dfs(v):
    id[v] = cur
    comps[-1].append(v)
    for to in g[v]:
        if id[to] == None:
            dfs(to)

id = [None] * nv
cur = 0
comps = []
for v in range(nv):
    if id[v] == None:
        comps.append([])
        dfs(v)
        cur += 1
bad = [0] * nv
for u, v in a:
    if id[u] == id[v]:
        bad[u] += 1
        bad[v] += 1
ret = [None] * nv
for v in range(nv):
    ret[v] = len(comps[id[v]]) - 1 - len(g[v]) - bad[v]
print(' '.join(map(str, ret)))

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.n = n
    self.g = [i for i in range(n)]
    self.nmembers = [1 for i in range(n)]
  def __len__(self):
    return self.n
  def __str__(self):
    return "group:{}\nnmembers:{}".format(self.g,self.nmembers)
  def __getitem__(self,x):
    return self.whichgroup(x)
  def merge(self, x, y):
    gx = self.whichgroup(x)
    gy = self.whichgroup(y)
    if gx != gy:
      nx = self.nmembers[gx]
      ny = self.nmembers[gy]
      ming = min(gx, gy)
      maxg = gx + gy - ming
      self.g[maxg] = ming
      self.nmembers[maxg] = 0
      self.nmembers[ming] = nx + ny
    
  def whichgroup(self, x):
    if x != self.g[x]:
      self.g[x] = self.whichgroup(self.g[x])
      self.nmembers[x] = 0
      return self.g[x]
    else:
      return x

N, M, K = map(int, input().split())
UF = UnionFind(N)
F = [0 for i in range(N)]
B = [0 for i in range(N)]

for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  
  UF.merge(x, y)
  F[x] += 1
  F[y] += 1
for i in range(K):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  
  gx = UF.whichgroup(x)
  gy = UF.whichgroup(y)
  if gx == gy:
    B[x] += 1
    B[y] += 1

ans = []
for i in range(N):
  ans.append(UF.nmembers[UF[i]]-B[i]-F[i]-1)
print(*ans)

Solution (Python):
from collections import deque
N, M, K = map(int, input().split())

flst = []
blst = []
glooplst = [i for i in range(N+1)]
colorlst = [0]*(N+1)
countlst = [0]*(N+1)
anslst = [0]*(N+1)
d = deque()

for i in range(N+1):
    flst.append([])
    blst.append([])


for i in range(M):
    a, b = map(int, input().split())
    flst[a].append(b) 
    flst[b].append(a)


for i in range(K):
    a, b = map(int, input().split())
    blst[a].append(b)
    blst[b].append(a)


for i in range(1, N+1):
    if colorlst[i] == 0:
        d.append(i)
        colorlst[i] = 1
        countlst[i] += 1
        while d:
            now = d.popleft()
            for j in flst[now]:
                if colorlst[j] == 0:
                    d.append(j)
                    colorlst[j] = 1
                    glooplst[j] = i
                    countlst[i] += 1

for i in range(1, N+1):
    cnt = countlst[glooplst[i]] - len(flst[i]) -1
    for j in blst[i]:
        if glooplst[i] == glooplst[j]:
            cnt -= 1

    print(cnt, end=' ')

print()

Solution (Python):
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        
        

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets

n,m,k=sep()
d=MergeFind(n)
temp=[]
for _ in range(m):
    a,b=sep()
    a -= 1
    b -= 1
    temp.append((a,b))
    d.merge(a,b)
ans=[0]*n
for i in range(n):
    ans[i]=d.set_size(i)-1
for _ in range(k):
    a, b = sep()
    a -= 1
    b -= 1
    temp.append((a, b))
for i in temp:
    a,b=i
    if d.find(a)==d.find(b):
        ans[a]-=1
        ans[b]-=1
print(*ans)

Solution (Python):
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    def find(self, x):
        if(self.parents[x] < 0):
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
        
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if(x == y):
            return
        
        if(self.parents[x] > self.parents[y]):
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}:{}'.format(r, self.members(r)) for r in self.roots())

N, M, K = map(int, input().split())
uf = Unionfind(N)
f = [0 for _ in range(N)]
n = [0 for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    
    f[a] += 1
    f[b] += 1
    
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if(uf.same(c, d)):
        n[c] += 1
        n[d] += 1
    
ans = []
for i in range(N):
    ans.append(uf.size(i)-f[i]-n[i]-1)
    
print(*ans)

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

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

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

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

for _ in range(K):
    c, d = map(int, input().split())
    if uf.same(c, d):
        B[c] += 1
        B[d] += 1

for i in range(1, N+1):
    ans = uf.size(i) - F[i] - B[i] - 1
    print(ans, end=' ')

print()

Solution (Python):
n,m,k = map(int,input().split())
import collections
par = []
for i in range(n):
    par.append(i)  
rank = [1 for i in range(n)] 
flist = [[] for i in range(n)]
blist = [[] for i in range(n)]
cut = []
def find(n): 
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): 
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): 
    x = find(a)
    y = find(b) 
    if x == y: 
        return    
    if rank[x] < rank[y]:
        par[x] = y 
    elif rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    else:
        par[y] = x
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    flist[a].append(b)
    flist[b].append(a)
    unite(a,b)
for i in range(n):
    shorten(i)
for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if par[a] == par[b]:
        blist[a].append(b)
        blist[b].append(a)
c = collections.Counter(par)
for i in range(n):
    ans = c[par[i]] -len(flist[i])-len(blist[i])-1
    print(ans,end = ' ')

Solution (Python):
from _collections import deque
n,m,k=map(int,input().split())
import sys
sys.setrecursionlimit(10**9) 

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

def s(y):
    global i
    if x[y]>0:
        return
    x[y]=i
    for j in fre[y]:
        if x[j]==-1:
            s(j)

for i in range(1,n+1):
    s(i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Solution (Python):
from _collections import deque
n,m,k=map(int,input().split())
import sys
sys.setrecursionlimit(10**9) 

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

def s(z,y):
    if x[y]>0:
        return
    x[y]=z
    for i in fre[y]:
        if x[i]==-1:
            s(z,i)

for i in range(1,n+1):
    s(i,i)

g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

Solution (Python):
from _collections import deque
n,m,k=map(int,input().split())

fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]

x=[-1]*(n+1)

for i in range(1,n+1):
    if x[i]==-1:
        x[i]=i
        data=deque([i])
        while len(data)>0:
            p=data.popleft()
            for j in fre[p]:
                if x[j]==-1:
                    x[j]=i
                    data.append(j)
g=[0]*(n+1)
for i in range(1,n+1):
    g[x[i]]+=1
for i in range(1,n+1):
    g[i]=g[x[i]]

for i in range(1,n+1):
    aa=g[i]-1
    aa-=len(fre[i])
    for j in bro[i]:
        if x[i]==x[j]:
            aa-=1
    ans.append(str(aa))
print(" ".join(ans))

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

import sys
sys.setrecursionlimit(10**9) 

root=[-1 for i in range(n+1)] 

def r(x):   
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x


fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]
for i in range(1,n+1):
    anser=-root[r(i)]-1
    anser-=len(fre[i])
    for j in bro[i]:
        if r(i)==r(j):
            anser-=1
    ans.append(str(anser))
print(" ".join(ans))

Solution (Python):
def LI():
    return list(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)]


N, M, K = LI()
par = [-1]*N
not_kouho = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
    not_kouho[a-1].append(b-1)
    not_kouho[b-1].append(a-1)

for i in range(K):
    a, b = map(int, input().split())
    if same(a-1, b-1):
        not_kouho[a-1].append(b-1)
        not_kouho[b-1].append(a-1)

for i in range(N):
    print(size(i)-len(not_kouho[i])-1, end=" ")

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            if x > y:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return

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

u = UnionFind(n)
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
    u.unite(a, b)
for c, d in cd:
    c, d = c-1, d-1
    l[c].add(d)
    l[d].add(c)
ans = [0] * n
for i in range(n):
    r = u.root(i)
    bl = 0
    for j in l[i]:
        if u.root(j) == r:
            bl += 1
    ans[i] = -u.parents[r] - len(f[i]) - bl - 1
print(*ans)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

        def __repr__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

        def find(self, x: int) -> int:
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int) -> int:
            """x,yが属する木をunion"""
            
            
            
            
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            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 same(self, x: int, y: int) -> bool:
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    N,M,K=MI()
    uf=UnionFind(N)
    F=[0]*N
    B=[0]*N
    
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        F[a]+=1
        F[b]+=1
        uf.union(a,b)
        
    for i in range(K):
        a,b=MI()
        a-=1
        b-=1
        if uf.same(a,b):
            B[a]+=1
            B[b]+=1
        
    ans=[]
    for i in range(N):
        aaa=uf.count(i)-1
        aaa-=F[i]+B[i]
        ans.append(aaa)
        

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

main()

Solution (Python):
from collections import deque
N,M,K = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
col = [-1 for _ in range(N+1)]
cnt = 0
for i in range(1,N+1):
    if col[i]<0:
        col[i] = cnt
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if col[y]<0:
                    col[y] = cnt
                    que.append(y)
        cnt += 1
C = {}
for i in range(1,N+1):
    c = col[i]
    if c not in C:
        C[c] = 0
    C[c] += 1
B = {i:[] for i in range(1,N+1)}
for _ in range(K):
    c,d = map(int,input().split())
    B[c].append(d)
    B[d].append(c)
A = []
for i in range(1,N+1):
    c = col[i]
    cnt = C[c]-len(G[i])-1
    for y in B[i]:
        if col[y]==c:
            cnt -= 1
    A.append(cnt)
print(*A)

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

import sys
sys.setrecursionlimit(10**9) 

root=[-1 for i in range(n+1)] 

def r(x):   
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x


fre=[[] for _ in range(n+1)]
bro=[[] for _ in range(n+1)]

for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
    fre[a].append(b)
    fre[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    bro[a].append(b)
    bro[b].append(a)

ans=[]
for i in range(1,n+1):
    anser=-root[r(i)]-1
    anser-=len(fre[i])
    for j in bro[i]:
        if r(i)==r(j):
            anser-=1
    ans.append(str(anser))
print(" ".join(ans))

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, K = mapint()

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

uf = UnionFind(N)
blocks = set()
friends = [0]*N
possi = [0]*N
for _ in range(M):
    a, b = mapint()
    uf.union(a-1, b-1)
    friends[a-1] += 1
    friends[b-1] += 1
for _ in range(K):
    a, b = mapint()
    if uf.same(a-1, b-1):
        friends[a-1] += 1
        friends[b-1] += 1
for i in range(N):
    possi[i] = uf.size(i)-friends[i]-1
print(*possi)

Solution (Python):
import sys

from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


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

    
    def get_size(self, x):
        return -self.parents[self.find(x)]

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


def main():
    n, m, k = input_int_list()
    union = UnionFind(n + 1)
    friends = defaultdict(set)
    blocks = defaultdict(set)

    for i in range(m):
        a, b = input_int_list()
        friends[a].add(b)
        friends[b].add(a)
        union.unite(a, b)

    for j in range(k):
        a, b = input_int_list()
        
        if union.same(a, b):
            blocks[a].add(b)
            blocks[b].add(a)
    ans = []
    for i in range(1, n + 1):
        ans.append(union.get_size(i) - len(friends[i]) - len(blocks[i]) - 1)

    print(*ans)
    return


if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M,K = map(int,input().split())
uf = UnionFind(N)
f_num = [0 for _ in range(N)] 
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1
  uf.union(a,b)
  f_num[a] += 1; f_num[b] += 1
ans = [-1 for _ in range(N)]
for i in range(N):
  temp = uf.get_size(i) - (1+f_num[i])
  ans[i] = temp
for i in range(K):  
  c,d = map(int,input().split())
  c-=1;d-=1
  if uf.is_same(c,d): 
    ans[c] -= 1
    ans[d] -= 1
print(*ans,sep="\n")

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 get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m,k = map(int, input().split())
uf = UnionFind(n+1)
direct_cnts = [0]*(n+1)

for _ in range(m):
    a,b = map(int, input().split())
    uf.union(a,b)
    direct_cnts[a] += 1
    direct_cnts[b] += 1


block = [[] for _ in range(n+1)]
for _ in range(k):
    c,d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)


ansl = []
for i in range(1,n+1):
    cnt = uf.size(i)-1
    cnt -= direct_cnts[i]
    for b in block[i]:
        if uf.same(i,b): cnt -= 1
    ansl.append(cnt)

print(*ansl)

Solution (Python):
N,M,K=map(int,input().split())
par=[0]*(N+1)
num=[0]*(N+1)
group = [1]*(N+1)

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

def root(x):
  if par[x]==x: return x
  return root(par[x])

def union(x,y):
  rx = root(x)
  ry = root(y)
  if rx==ry: return
  par[max(rx,ry)] = min(rx,ry)
  group[min(rx,ry)] += group[max(rx,ry)]

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

for _ in range(M):
  a,b=map(int,input().split())
  union(a,b)
  num[a]+=1
  num[b]+=1
for _ in range(K):
  c,d=map(int,input().split())
  if same(c,d):
    num[c]+=1
    num[d]+=1

for i in range(1,N+1):
  print(group[root(i)]-num[i]-1,end=" ")

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

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


def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

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

for i in range(m):
    a,b=map(int,input().split())
    union(a-1,b-1)
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

for i in range(k):
    a,b=map(int,input().split())
    if find(a-1)==find(b-1):
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

ans=[]

for i in range(n):
    cnt=size[find(i)]
    xxx=list(set(graph[i]))
    cnt-=len(xxx)
    cnt-=1
    ans+=[str(cnt)]


print(' '.join(ans))

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

class UnionFind():
    
    
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        self.group = n
    
    
    def root(self, x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    
    def union(self, x, y):
        x = self.root(x)
        y = self.root(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
        self.group -= 1
    
    
    def same(self, x, y):
        return self.root(x)==self.root(y)

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


N,M,K=mint()
T=UnionFind(N)
block=[0]*N
for _ in range(M):
    a,b=mint()
    T.union(a-1,b-1)
    block[a-1]+=1
    block[b-1]+=1
for _ in range(K):
    c,d=mint()
    if T.same(c-1,d-1):
        block[c-1]+=1
        block[d-1]+=1
ans=[T.size(i)-block[i]-1 for i in range(N)]
lprint(ans,' ')