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 Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().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())

n,m,k = inpl()
ab = [inpl() for i in range(m)]
cd = [inpl() for i in range(k)]
uf = UnionFind(n)
fr = [[] for i in range(n)]
bl = [[] for i in range(n)]
for i in range(m):
    a,b = ab[i]
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
    uf.union(a-1,b-1)
for i in range(k):
    c,d = cd[i]
    bl[c-1].append(d-1)
    bl[d-1].append(c-1)

for i in range(n):
    s = set()
    cnt = 0
    for j in fr[i]:
        s.add(j)
    for j in bl[i]:
        if uf.same(i,j) and not j in s:
            cnt += 1
    print(uf.size(i)-1 - len(s) - cnt)

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

blocks=[set() for _ in range(n)]
for c,d in CD:
  c,d=c-1,d-1
  blocks[c].add(d)
  blocks[d].add(c)

friends=[0]*n
uf=UnionFind(n)
for a,b in AB:
  a,b=a-1,b-1
  friends[a]+=1
  friends[b]+=1
  if not uf.is_same(a,b): uf.union(a,b)
    
ctr=Counter()
for i in range(n):
  r=uf.root(i)
  ctr[r]+=1
  
ans=[]
for i in range(n):
  tmp=ctr[uf.root(i)]-friends[i]-1
  for b in blocks[i]:
    if uf.is_same(i,b): tmp-=1
  ans.append(tmp)
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
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 solve():
  n,m,k = (int(i) for i in input().split())
  uff = UnionFind(n)
  ufb = UnionFind(n)
  query = [0]*n
  query2 = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i)-1 for i in input().split())
    uff.union(a,b)
    query[a] += 1
    query[b] += 1
    query2[a].append(b)
    query2[b].append(a)
  for i in range(k):
    a,b = (int(i)-1 for i in input().split())
    if uff.same(a,b):
      ufb.union(a,b)
      query2[a].append(b)
      query2[b].append(a)
  for i in range(n):
    print(uff.size(i)-1-len(query2[i]), end=" ")
solve()

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

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

V = [[] for _ in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  V[a].append(b)
  V[b].append(a)


L = [0 for _ in range(N)]
def dfs(u,l):
  L[u] = l
  for t in V[u]:
    if L[t] == 0:
      dfs(t,l)

l = 1
for i in range(N):
  if L[i] == 0:
    dfs(i,l)
    l += 1

C = {}
for ll in L:
  if ll in C:
    C[ll] += 1
  else:
    C[ll] = 1

ans = [C[L[i]]-1 for i in range(N)]
for a,b in AB:
  a -= 1
  b -= 1
  ans[a] -= 1
  ans[b] -= 1
for c,d in CD:
  c -= 1
  d -= 1
  if L[c] == L[d]:
    ans[c] -= 1
    ans[d] -= 1
print(*ans)

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)
    
N, M, K = map(int, input().split())
U = UnionFind(N)
ng = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    U.union(a-1, b-1)
    ng[a-1] += 1
    ng[b-1] += 1
for i in range(K):
    c, d = map(int, input().split())
    if U.same(c-1, d-1): 
        ng[c-1] += 1
        ng[d-1] += 1
li = []
for i in range(N):
    li.append(U.size(i)-ng[i]-1)
print(*li)

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

connected = [list(map(int, input().split())) for _ in range(M)]
blocked = [list(map(int, input().split())) for _ in range(K)]


class UnionFind(object):
    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)


uf = UnionFind(N)
num_remove = [0] * N

for a, b in connected:
    uf.union(a - 1, b - 1)

for a, b in connected:
    if uf.same(a - 1, b - 1):
        num_remove[a - 1] += 1
        num_remove[b - 1] += 1

for c, d in blocked:
    if uf.same(c - 1, d - 1):
        num_remove[c - 1] += 1
        num_remove[d - 1] += 1


ret = []
for i in range(N):
    ret.append(str(uf.size(i) - num_remove[i] - 1))


print(' '.join(ret))

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())
uf = UnionFind(N)
dir_or_blk = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dir_or_blk[a].append(b)
    dir_or_blk[b].append(a)
    uf.union(a, b)

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

for i in range(N):
    ans = uf.size(i)-len(dir_or_blk[i])-1
    print(ans, end=" ")

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())
uf = UnionFind(N)

friend_cnt = [0] * N
for i in range(M):
    A,B = map(lambda x:int(x)-1,input().split())
    uf.union(A,B)
    friend_cnt[A]+=1
    friend_cnt[B]+=1
    
block_cnt = [0] * N
for i in range(K):
    C,D = map(lambda x:int(x)-1,input().split())
    if uf.same(C,D):
        block_cnt[C]+=1
        block_cnt[D]+=1
        
print(' '.join(map(lambda i:str(uf.size(i)-friend_cnt[i]-block_cnt[i]-1), range(N))))

Solution (Python):

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

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            fring[frnfrom] = []

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd] and frno[cc] != -1:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Solution (Python):

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

fcnum = [ 0 for i in range(N+1)]
fring = [[] for i in range(N+1)]
frno =  [-1 for i in range(N+1)]

ab = []
for i in range(M):
    aa,bb = map(int, input().split())
    if aa > bb:
        aa,bb = bb,aa
    fcnum[aa] -= 1
    fcnum[bb] -= 1
    ab.append([aa,bb])

for aa,bb in ab:
    if frno[aa] == -1 and frno[bb] == -1:
        frn = aa
        frno[aa] = frn
        frno[bb] = frn
        fring[frn].append(aa)
        fring[frn].append(bb)
    elif frno[aa] == -1 and frno[bb] != -1:
        frn = frno[bb]
        frno[aa] = frn
        fring[frn].append(aa)
    elif frno[aa] != -1 and frno[bb] == -1:
        frn = frno[aa]
        frno[bb] = frn
        fring[frn].append(bb)
    else:
        if frno[aa] != frno[bb]:
            if len(fring[frno[aa]]) > len(fring[frno[bb]]):
                frnto = frno[aa]
                frnfrom = frno[bb]
            else:
                frnto = frno[bb]
                frnfrom = frno[aa]
            fring[frnto].extend(fring[frnfrom])
            for mvf in fring[frnfrom]:
                frno[mvf] = frnto
            fring[frnfrom] = []

for i in range(K):
    cc,dd = map(int, input().split())
    if frno[cc] == frno[dd] and frno[cc] != -1:
        fcnum[cc] -= 1
        fcnum[dd] -= 1

for k in range(1,len(fring)):
    cnum = len(fring[k]) - 1
    for ff in fring[k]:
        fcnum[ff] += cnum

for i in range(1,len(fcnum)):
    print(fcnum[i]," ",end="")

Solution (Python):
N, M, K = map(int,input().split())
uf = [-1 for _ in range(N)]
fc = [0] * N
bc = [0] * N
ans = [0] * N

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

def unite(x, y):
    
    x = find(x)
    y = find(y)
    if x == y:
        return
    if x < y:
        x , y = y, x
    uf[y] += uf[x]
    uf[x] = y

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

for k in range(K):
    c, d = map(int,input().split())
    if find(c-1) == find(d-1):
        bc[c-1] += 1
        bc[d-1] += 1

for i in range(N):
    cnt = -uf[find(i)] - 1 - fc[i] - bc[i]
    ans[i] = cnt

print(*ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)
 
    def find(self, x):
        if self.parents[x] == x:
            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 y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]

def main():
    n, m, k = map(int, input().split())
    uf = UnionFind(n)
    friends = [0] * n
    blocks = [0] * n
    for i in range(m):
        a, b = map(int, input().split())
        friends[a - 1] += 1
        friends[b - 1] += 1
        uf.unite(a - 1, b - 1)
    for i in range(k):
        c, d = map(int, input().split())
        if uf.same(c - 1, d - 1):
            blocks[c - 1] += 1
            blocks[d - 1] += 1
    ans = [0] * n
    for i in range(n):
        ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
    print(*ans)      

if __name__ == '__main__':
  main()

Solution (Python):
from collections import deque

def main():
    n, m, k = [int(e) for e in input().split()]

    Df, Db = {}, {}
    for i in range(1, n + 1):
        Df[i] = set()
        Db[i] = set()

    for i in range(m):
        a, b = [int(e) for e in input().split()]
        Df.get(a).add(b)
        Df.get(b).add(a)

    for i in range(k):
        c, d = [int(e) for e in input().split()]
        Db.get(c).add(d)
        Db.get(d).add(c)

    Q = deque()
    C = set()
    ANS = {}
    for i in range(1, n + 1):
        if i in C:
            continue

        C.add(i)
        Cin = set()
        Cin.add(i)
        Q.appendleft(i)
        while len(Q) != 0:
            for f in Df.get(Q.pop()) - Cin:
                Q.appendleft(f)
                C.add(f)
                Cin.add(f)

        for k in Cin:
            ANS[k] = len(Cin) - len(Df[k]) - len(Cin & Db[k] - Df[k]) - 1

    print(*[ANS[i] for i in range(1, n + 1)])

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


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

    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 False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

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

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


d = DisjointSet(N)
friends = defaultdict(int)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai] += 1
    friends[Bi] += 1
blocking = defaultdict(list)
for Ci, Di in B:
    blocking[Ci].append(Di)
    blocking[Di].append(Ci)

ans = [0] * N
for i in range(N):
    ans[i] = d.size(i) - friends[i] - 1
    for b in blocking[i]:
        if d.same(i, b):
            ans[i] -= 1
print(' '.join(list(map(str, ans))))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            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 y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)

Solution (Python):

class Unionfind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] = self.d[x] + self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.d[self.find(x)]

n, m, k = map(int, input().split())
dame = [set() for _ in range(n)]
uf = Unionfind(n)

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dame[a].add(b)
    dame[b].add(a)
    uf.unite(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    mem = uf.size(i) - 1
    mem -= len(dame[i])
    print(mem, end= " ")
print()

Solution (Python):

class Unionfind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] = self.d[x] + self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.d[self.find(x)]

n, m, k = map(int, input().split())
dame = [set() for _ in range(n)]
uf = Unionfind(n)

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dame[a].add(b)
    dame[b].add(a)
    uf.unite(a, b)

for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if not uf.same(c, d):
        continue
    dame[c].add(d)
    dame[d].add(c)

for i in range(n):
    mem = uf.size(i) - 1
    mem -= len(dame[i])
    print(mem, end= " ")
print()

Solution (Python):

from collections import Counter
N,M,K = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
CD = [tuple(map(int,input().split())) for i in range(K)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

blocks = [[] for _ in range(N)]
for c,d in CD:
    c,d = c-1,d-1
    blocks[c].append(d)
    blocks[d].append(c)

friends = [0] * N
uf = UnionFind(N)
for a,b in AB:
    a,b = a-1,b-1
    friends[a] += 1
    friends[b] += 1
    if uf.is_same(a,b): continue
    uf.unite(a,b)
for i in range(N):
    uf.root(i)

ctr = Counter()
for i in range(N):
    r = uf.root(i)
    ctr[r] += 1

ans = []
for i in range(N):
    tmp = ctr[uf.root(i)] - 1 - friends[i]
    for b in blocks[i]:
        if uf.is_same(i,b):
            tmp -= 1
    ans.append(tmp)
print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]
rank = [0]*(N+1)

def union(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return
    if rank[x]<rank[y]:
        parent[x]=y
    else:
        parent[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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





for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1


kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]
rank = [0]*(N+1)

def union(x,y):
    x = find(x)
    y = find(y)
    if x==y:
        return
    if rank[x]<rank[y]:
        parent[x]=y
    else:
        parent[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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





for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    












kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

Solution (Python):
import sys
read=sys.stdin.buffer.read
readline=sys.stdin.readline
readlines=sys.stdin.buffer.readlines


class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  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:
      return
    if self.size[x]>self.size[y]:
      
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
N,M,K=map(int,readline().split())
UF=UnionFind(N)
friends=[0]*N
for i in range(M):
  a,b=map(int,readline().split())
  UF.unite(a-1,b-1)
  friends[a-1]+=1
  friends[b-1]+=1

from collections import defaultdict
block=defaultdict(set)
for i in range(K):
  c,d=map(int,readline().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)

ans=[0]*N
for i in range(N):
  ans[i]=UF.get_group_size(i)-friends[i]-1
  for b in block[i]:
    if UF.same(i,b):
      ans[i]-=1
  if ans[i]<0:
    ans[i]=0
print(*ans)

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)    

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

uf = UnionFind(n)
A = {i:[] for i in range(n)}
for i in range(m):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  A[a].append(b)
  A[b].append(a)
  uf.union(a,b)
  
C = {i:[] for i in range(n)}
for i in range(k):
  c,d = map(int,input().split())  
  c,d = c-1,d-1
  if uf.same(c,d):
    C[c].append(d)
    C[d].append(c)
  
ans = [0]*n
for i in range(n):    
  ans[i] = uf.size(i) - len(A[i]) - len(C[i]) - 1  
print(*ans)

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

N, M, K = map(int, input().split())
friends = {i: set() for i in range(N)}
blocks = {i: set() for i in range(N)}

for _ in range(M):
    a, b = map(int, input().split())
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

for _ in range(K):
    a, b = map(int, input().split())
    blocks[a-1].add(b-1)
    blocks[b-1].add(a-1)

counts = [0] * N
seen = [False] * N
def dfs(v):
    if seen[v] == True:
        return
    seen[v] = True
    for node in friends[v]:
        c.add(node)
        dfs(node)
 
for v in range(N):
    if seen[v] == True:
        continue
    c = set()
    dfs(v)
    l = len(c)
    for i in c:
        counts[i] = l - 1
        counts[i] -= len(c & friends[i])
        counts[i] -= len(c & blocks[i])
print(' '.join(map(str, counts)))