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

Solution (Python):


import sys
import math
import itertools

def main():
    n, m, k = map(int, sys.stdin.readline().split())
    fs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]
    bs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(k)]

    g = [[] for _ in range(n)]
    for u, v in fs:
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)

    bg = [[] for _ in range(n)]
    for u, v in bs:
        bg[u - 1].append(v - 1)
        bg[v - 1].append(u - 1)

    ccmembs = []
    ccmap = [-1] * n
    def color_component(ccid, root):
        stack = [root]
        ccmap[root] = ccid
        nmemb = 1
        while len(stack) > 0:
            u = stack.pop()
            for v in g[u]:
                if ccmap[v] < 0:
                    ccmap[v] = ccid
                    nmemb += 1
                    stack.append(v)
        return nmemb

    for u in range(n):
        if ccmap[u] < 0:
            ccmembs.append(color_component(len(ccmembs), u))

    for u in range(n):
        c = (ccmembs[ccmap[u]]
                - sum(1 for v in g[u] if ccmap[u] == ccmap[v])
                - sum(1 for v in bg[u] if ccmap[u] == ccmap[v])
                - 1)
        print(c, end=(' ' if u != n - 1 else '\n'))

if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


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

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.getCount(i) - 1 for i in range(N)]


for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in CD:
    if G.same(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Solution (Python):
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))

class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)
        self.size = [1] * N  
        self.blocksize = [0] * N

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

    def block(self, x, y):
        if not self.has_same_parent(x, y):
            return
        self.blocksize[x] += 1
        self.blocksize[y] += 1

    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.tree[x] = y
            self.size[y] += self.size[x]
        else:
            self.tree[y] = x
            self.size[x] += self.size[y]

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

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


N, M, K = MI()
uf = UnionFind(N)
nl = [set() for _ in range(N)]
for _ in range(M):
    A, B = MI()
    nl[A - 1].add(B - 1)
    nl[B - 1].add(A - 1)
    uf.unite(A - 1, B - 1)

for _ in range(K):
    C, D = MI()
    uf.block(C - 1, D - 1)


ans = []
for i in range(N):
    a = uf.component_size(i) - len(nl[i]) - uf.blocksize[i] - 1
    ans.append(str(a))
print(' '.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    def find(self, x):
        
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_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:
            return 
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
u = UnionFind(n)
ans_li = [-1 for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    ans_li[a] -= 1
    ans_li[b] -= 1
for i in range(k):
    a,b = map(int, input().split())
    if u.find(a) == u.find(b):
        ans_li[a] -= 1
        ans_li[b] -= 1
for i in range(1,n+1):
    ans_li[i] += u.getsize(i)
    print(ans_li[i], end = " ")

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

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

    def unite(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.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

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


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M
C, D = [0] * K, [0] * K



g_direct =[[] for _ in range(N)]
uf = UnionFind(N)  

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    g_direct[A[i]].append(B[i])
    g_direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    if uf.same(C[i], D[i]):  
        g_direct[C[i]].append(D[i])
        g_direct[D[i]].append(C[i])


ans = [0] * N

for i in range(N):
    ans[i] = uf.group_size(i) - len(g_direct[i]) - 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)

    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=list(map(int,input().split()))

candFriends=UnionFind(n)
elim=[0]*n

for i in range(m):
    a,b=list(map(lambda x:int(x)-1,input().split()))
    candFriends.union(a,b)
    
    elim[a]-=1
    elim[b]-=1

for i in range(k):
    c,d=list(map(lambda x:int(x)-1,input().split()))

    rootc=candFriends.find(c)
    rootd=candFriends.find(d)

    if rootc==rootd:
        elim[c]-=1
        elim[d]-=1


print(' '.join([str(candFriends.size(i)+elim[i]-1) for i in range(n)]))

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

class UnionFind_size:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.size = [1] * (n+1)
    
    
    def find(self, x):
        
        if self.par[x] == x:
            return x
        
        else:
            
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    
    def unite(self, x, y):
        
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    
    def get_size(self, x):
        return self.size[self.find(x)]
    
    
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    N,M,K = map(int, readline().split())

    uf = UnionFind_size(N+1)
    F = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        F[a].append(b)
        F[b].append(a)
        uf.unite(a, b)
    
    B = [[] for _ in range(N+1)]
    for _ in range(K):
        c,d = map(int, readline().split())
        B[c].append(d)
        B[d].append(c)


    ans = []
    for i in range(1,N+1):
        tmp = 0
        tmp += uf.get_size(i) - 1
        tmp -= len(F[i])
        for j in B[i]:
            if uf.same_check(i, j):
                tmp -= 1
        ans.append(tmp)
    
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

N, M, K = map(int, input().split())
friends = [set(map(int, input().split())) for _ in range(M)]
blocks = [set(map(int, input().split())) for _ in range(K)]

ans = [0] * N
uf = UnionFind(N)
for a, b in friends:
    uf.union(a - 1, b - 1)
    ans[a - 1] -= 1
    ans[b - 1] -= 1
    
for c, d in blocks:
    if uf.same(c - 1, d - 1):
        ans[c - 1] -= 1
        ans[d - 1] -= 1

for i in range(N):
    ans[i] += uf.size(i)-1
print(*ans)

Solution (Python):


from collections import Counter

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

fn = [1]*N
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

	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 unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0

		return

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

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

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

block = [[] for _ in range(n)]
for _ in range(k):
	a, b = map(int, input().split())
	block[a-1].append(b-1)
	block[b-1].append(a-1)

ans = []
for i in range(n):
	res = uf.get_size(i) - 1 - len(friend[i])
	for v in block[i]:
		if uf.find(i) == uf.find(v):
			res -= 1
	ans.append(res)

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 unite(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 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 size(self,x):
        return -self.parents[self.find(x)]
    
    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())
    F=[tuple(map(int,input().split())) for _ in range(m)]
    B=[tuple(map(int,input().split())) for _ in range(k)]
   

    uf=UnionFind(n)
    for a,b in F:
        a-=1
        b-=1
        uf.unite(a,b)
      
    cnt=[0]*n
    for i in range(n):
        cnt[i]=uf.size(i)-1
    
    for a,b in F:
        a-=1
        b-=1
        if uf.same(a,b):
            cnt[a]-=1
            cnt[b]-=1
    
    for c,d in B:
        c-=1
        d-=1
        if uf.same(c,d):
            cnt[c]-=1
            cnt[d]-=1
    print(*cnt)
   
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 FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  cnt[a]+=1
  cnt[b]+=1
  t.Unite(a,b)
for _ in range(k):
  a,b=map(int,input().split())
  if t.isSameGroup(a,b)==True:
    cnt[a]+=1
    cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
  ans[i]=(t.Count(i)-1)-cnt[i]
print(*ans[1:])

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

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

N, M, K = map(int, readline().split())
m = map(int,read().split())
fb = list(zip(m,m))

AB = fb[:M]
CD = fb[M:]
uf = UnionFind(N+1)
friends = [[] for i in range(N+1)]
for a, b in AB:
    uf.union(a, b)
    friends[a].append(b)
    friends[b].append(a)

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

ans = []
for i in range(1, N+1):
    same_tree_size = uf.size(i)
    same_tree_block = 0
    for x in blocks[i]:
        same_tree_block += uf.same(i, x)
    n_friends = len(friends[i])
    
    
    
    
    
    ans.append(str(same_tree_size - same_tree_block - n_friends - 1))

print(' '.join(ans))

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

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

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = parent
			while True:
				tmp = self.groups[root]
				if tmp == root:
					break
				root = tmp
			
			while i != root:
				tmp = self.groups[i]
				self.groups[i] = root
				i = tmp
			
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		while parent != root:
			self.groups[i] = root
			i = parent
			parent = self.groups[i]
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def counts(self):
		table = [None] * len(self.groups)
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if table[g] != None:
				table[g] += 1
			else:
				table[g] = 1
		
		ret = [0] * len(self.groups)
		
		for i in range(len(self.groups)):
			ret[i] = table[self.get_root(i)]
		
		return ret
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]


groups = UnionFind(N)
minus_list = [0] * N

for _ in range(M):
	a, b = map(lambda x: int(x) - 1, input().split())
	groups.combine(a, b)
	minus_list[a] -= 1
	minus_list[b] -= 1

for _ in range(K):
	c, d = map(lambda x: int(x) - 1, input().split())
	if groups.in_same_group(c, d):
		minus_list[c] -= 1
		minus_list[d] -= 1

counts = groups.counts()

print(" ".join((str(counts[i] + minus_list[i] - 1) for i in range(N))))

Solution (Python):
from collections import defaultdict
from collections import Counter

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

fn = [1]*N
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

Solution (Python):
from collections import defaultdict, Counter
import sys

def root(uft, x):
    if uft[x] == x: return x
    uft[x] = root(uft, uft[x])
    return uft[x]

def union(uft, rank, x, y):
    x = root(uft, x)
    y = root(uft, y)
    if x == y:
        return

    if rank[x] >= rank[y]:
        uft[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        uft[x] = y

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

def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(int)
    block = defaultdict(int)
    group = defaultdict(set)
    uft = [i for i in range(n+1)]
    rank = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        union(uft, rank, a, b)
        friend[a] += 1
        friend[b] += 1
    for j in range(k):
        c, d = map(int, input().split())
        if not same(uft, c, d):
            continue
        block[c] += 1
        block[d] += 1
    for i in range(1, n+1):
        root(uft, i)
    c = Counter(uft)
    return [c[uft[i]]-block[i]-friend[i]-1 for i in range(1, n+1)]

print(*answer())

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)
    


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

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

for _ in range(K):
    a,b = map(int, input().split())
    if uf.same(a-1,b-1):
        block[a-1] += 1
        block[b-1] += 1

result = [uf.size(i) - friend[i] - block[i] - 1 for i in range(N)]
print(' '.join(map(str, result)))

Solution (Python):
from collections import Counter

def main():
    n, m, k = [int(s) for s in input().strip().split()]
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = [int(s) for s in input().strip().split()]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    
    groups = [-1] * n
    for i in range(n):
        if groups[i] < 0:
            groups[i] = i
            q = [i]
            for j in q:
                for v in adj[j]:
                    if groups[v] < 0:
                        groups[v] = i
                        q.append(v)
    cnt = Counter(groups)

    result = [cnt[groups[i]] - len(adj[i]) - 1 for i in range(n)]
    for _ in range(k):
        c, d = [int(s) for s in input().strip().split()]
        if groups[c - 1] == groups[d - 1]:
            result[c - 1] -= 1
            result[d - 1] -= 1
    print(" ".join(str(x) for x in result))


main()

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




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



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

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



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



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



par = [-1]*(N+1)


friend_list = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    unite(A,B)
    friend_list[A].append((B))
    friend_list[B].append((A))

block_list = [[] for _ in range(N+1)]
for _ in range(K):
    C, D = map(int, input().split())
    block_list[C].append(D)
    block_list[D].append(C)

anslist = [0]*(N)
for i in range(1,N+1):

    block_and_connect = 0
    for hito in block_list[i]:
        if same(hito,i):
            block_and_connect += 1
    ans = size(i) - 1 - len(friend_list[i]) - block_and_connect
    anslist[i-1] = ans
print(*anslist)

Solution (Python):
from collections import defaultdict
from collections import Counter

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

fn = defaultdict(lambda: 1)
CD = [0]*K

par = list(range(N))

def root(x):
    S = set()
    S.add(x)
    y = x
    while True:
        if par[y] == y:
            for s in S:
                par[s] = y
            return y
        S.add(y)
        y = par[y]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    par[rx] = ry

for _ in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    fn[A] += 1
    fn[B] += 1
    unite(A,B)
    
for _ in range(K):
    C,D = map(int,input().split())
    C -= 1
    D -= 1
    CD[_] = (C,D)

par = [root(x) for x in range(N)]
c = Counter(par)

RESULT = [(c[par[x]] - fn[x]) for x in range(N)]

for C,D in CD:
    if par[C] == par[D]:
        RESULT[C] -= 1
        RESULT[D] -= 1

print(*RESULT,sep=" ")

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

    def members(self, x):
        root = self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i) == 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()}

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


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

uf = UnionFind(n)
directcount = [0] * n

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

res = []
for _ in range(n):
    res.append( [0, -1] )
ures = []

for i in range(n):
    res[i][0] = uf.size(i) - directcount[i] -1
    res[i][1] = uf.Find_Root(i)



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


print(" ".join(list(map(lambda x: str(x[0]), res))))