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):
"""

AtCoder Beginner Contest 157  D - Friend Suggestions


友達関係でUnionを作る。そのUnion内で、友達関係でも、Union内のブロック関係でもないものが友達候補
なので、
・友達関係でUnionFindでUnion化し、
・それぞれのUnionに所属する人数を調べて、自分を除く所属人数を友達候補の候補（変な表現だが）として、
・自分と友達関係の個数＆おなじUnionかつブロック関係の個数を引く
でOK

"""

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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N



members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    
    ans[i] = members[uf.root(i)] - 1


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


for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

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, 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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N



members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    
    ans[i] = members[uf.root(i)] - 1


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


for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

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, 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

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

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

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

uf = UnionFind(N)

for a,b in friends:
    if not uf.is_same(a,b):
        uf.unite(a,b)

ans = [0] * N

for i in range(N):
    _ = uf.root(i)


members = [0] * N
for i in range(N):
    members[uf.root(i)] += 1

for i in range(N):
    
    ans[i] = members[uf.root(i)] - 1


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


for c,d in blocks:
    if uf.is_same(c,d):
        ans[c] -= 1
        ans[d] -= 1


print(*ans)

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

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

p=list(range(N))
r=[0]*N

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

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x]+=1

nc=[1]*N
f=[0]*N

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

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

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

print(*[f[find(i)]-nc[i] for i in range(N)])

Solution (Python):

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

p=[i for i in range(N)]
r=[0]*N

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

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x]+=1

nc=[1]*N
f=[0]*N

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

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

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

print(*[f[find(i)]-nc[i] for i in range(N)])

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


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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    friend = UF_tree(N)
    d = defaultdict(int)

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

    for _ in range(K):
        C, D = map(int, input().split())
        if friend.isSame(C, D):
            d[C] += 1
            d[D] += 1

    ans = [friend.getNodeLen(i) - d[i] - 1 for i in range(1, N + 1)]
    print(*ans)

Solution (Python):
class UF():
    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]
n,m,k = map(int,input().split())
uf=UF(n)
 
F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)
 
B=[0]*n
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

Solution (Python):
class UF():
    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]
n,m,k = map(int,input().split())
uf=UF(n)
 
F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)
 
B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

Solution (Python):
def init(n) :  
	for i in range(n) :
		par[i] = i;
		rank[i] = 0;
		siz[i] = 1;

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

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

def unite(x,y) :  
	x = root(x);
	y = root(y);
	if x == y :
		return;
	if siz[x] < siz[y] :
		x,y = y,x;
	siz[x] += siz[y];
	par[y] = x;

def size(x) :
	return siz[root(x)];


nmk = input().split(' ');
n = int(nmk[0]);
m = int(nmk[1]);
k = int(nmk[2]);

par = [0]*n
rank = [0]*n
siz = [0]*n
init(n);

fre = [[0]*2 for i in range(m)];
bro = [[0]*2 for i in range(k)];
fb = [0]*n;

for i in range(m) :
	ab = input().split(' ');
	unite(int(ab[0])-1,int(ab[1])-1);
	fb[int(ab[0])-1] += 1;
	fb[int(ab[1])-1] += 1;
	fre[i][0] = int(ab[0]);
	fre[i][1] = int(ab[1]);

for i in range(k) :
	ab = input().split(' ');
	bro[i][0] = int(ab[0]);
	bro[i][1] = int(ab[1]);

for i in range(k) :
	if root(bro[i][0]-1) == root(bro[i][1]-1) :
		fb[bro[i][0]-1] += 1;
		fb[bro[i][1]-1] += 1;

print(size(0)-fb[0]-1,end='');
for i in range(1,n) :
    print('',size(i)-fb[i]-1,end='');
print();

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]

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

F=[set() for _ in range(n)]
for i in range(m):
   a,b=map(int,input().split())
   uf.union(a-1,b-1)
   F[a-1].add(b-1)
   F[b-1].add(a-1)

B=[0 for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    if uf.same(c-1,d-1):
        B[c-1]-=1
        B[d-1]-=1
A=[]
for i in range(n):
    A.append(uf.size(i)-len(F[i])+B[i]-1)
print(*A)

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]

N, M, K = map(int,input().split())
uf = UnionFind(N)
F = [set() for k in range(N)]
for k in range(M):
    A, B = map(int,input().split())
    uf.union(A-1,B-1)
    F[A-1].add(B-1)
    F[B-1].add(A-1)

T = [0 for k in range(N)]
for k in range(K):
    C, D = map(int,input().split())
    if uf.same(C-1,D-1) == True:
        T[C-1] -= 1
        T[D-1] -= 1
A = []
for k in range(N):
    A.append(uf.size(k)-len(F[k])+T[k]-1)
print(*A)

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]

N, M, K = map(int,input().split())
uf = UnionFind(N)
F = [set() for k in range(N)]
for k in range(M):
    A, B = map(int,input().split())
    uf.union(A-1,B-1)
    F[A-1].add(B-1)
    F[B-1].add(A-1)

T = [0 for k in range(N)]
for k in range(K):
    C, D = map(int,input().split())
    if uf.same(C-1,D-1) == True:
        T[C-1] -= 1
        T[D-1] -= 1
A = []
for k in range(N):
    A.append(uf.size(k)-len(F[k])+T[k]-1)
print(*A)

Solution (Python):
def main():
    N, M, K = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

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

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

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

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

    fri = [[] for _ in range(N)]
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
        unite(a-1, b-1)
    block = [[] for _ in range(N)]
    for i in range(K):
        a, b = (int(i) for i in input().split())
        if is_same_group(a-1, b-1):
            block[a-1].append(b-1)
            block[b-1].append(a-1)
    ans = []
    for i in range(N):
        cur = size(i) - len(fri[i]) - len(block[i]) - 1
        ans.append(cur)
    print(*ans)


if __name__ == '__main__':
    main()

Solution (Python):
def Find(x, par):
  if par[x] < 0:
    return x
  else:
    
    par[x] = Find(par[x], par)
    return par[x]

def Unite(x, y, par, rank):
  x = Find(x, par)
  y = Find(y, par)

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

def Same(x, y, par):
  return Find(x, par) == Find(y, par)

def Size(x, par):
  return -par[Find(x, par)]

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

F = [0]*n
B = [0]*n

par = [-1]* n
rank = [0]*n

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

for i in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if Same(c, d, par):
        B[c] += 1
        B[d] += 1

ans = [0]*n
for i in range(n):
    ans[i] = Size(i, par)-F[i]-B[i]-1
print(*ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    CD = [tuple(map(int, input().split())) for _ in range(K)]

    uf = UnionFindTree(N)
    friend_or_block = [set() for _ in range(N)]
    for a, b in AB:
        a, b = a-1, b-1
        uf.union(a, b)
        friend_or_block[a].add(b)
        friend_or_block[b].add(a)
    for c, d in CD:
        c, d = c-1, d-1
        if uf.same(c, d):
            friend_or_block[c].add(d)
            friend_or_block[d].add(c)
    
    print(*[uf.size(i) - len(friend_or_block[i]) - 1 for i in range(N)])

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

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

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

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    
    def __init__(self, n):
        
        self.n = n
        
        
        self.parents = [-1] * n
 
    
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    
    def size(self, x):
        return -self.parents[self.find(x)]
 
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    
    def group_count(self):
        return len(self.roots())

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

    best_friend = [0] * N
    friend = UnionFind(N)
    for _ in range(M):
        A,B = map(int,input().split())
        best_friend[A-1] += 1
        best_friend[B-1] += 1
        friend.union(A-1, B-1)

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

    ans = [0] * N
    for i in range(N):
        
        ans[i] = friend.size(i) - best_friend[i] - 1
        
        for bad in blocked[i]:
            if friend.same(i, bad):
                ans[i] -= 1

    print(*ans, sep=" ")

if __name__ == "__main__":
    main()

Solution (Python):
import sys

class UFT(): 
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

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

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1



def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    parent = UFT(N)
    connect = dict()
    NG = [0] * N
    friend = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        parent.unite(x-1, y-1)
        friend[x-1] += 1
        friend[y-1] += 1
    for i in range(N):
        key = parent.find(i)
        if key in connect: connect[key] += 1
        else: connect[key] = 1
    for _ in range(K):
        c, d = map(int, input().split())
        if parent.find(c-1) == parent.find(d-1):
            NG[c-1] += 1
            NG[d-1] += 1
    Ans = [0] * N
    for i in range(N):
        Ans[i] = connect[parent.find(i)] - friend[i] - NG[i] - 1
    print(" ".join(map(str, Ans)))

    return 0

if __name__ =="__main__":
    solve()

Solution (Python):
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
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)
for a,b in ab:u.unite(a-1,b-1)
ans=[u.count(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 u.root_same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)

Solution (Python):
import sys
from collections import Counter
N,M,K = map(int,input().split())
f = [[] for _ in range(N+1)]
b = [[] for _ in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    f[x].append(y)
    f[y].append(x)

d = [None]*(N+1)
sys.setrecursionlimit(10**9)
def dfs(f,s,id):
    if(d[s] is None):
        d[s] = id
    for i in f[s]:
        if(d[i] is not None):
            continue
        dfs(f,i,id)
         
cnt = -1
for j in range(1,N+1):
    if(d[j] == None):
        cnt += 1
        dfs(f,j,cnt)
    
for i in range(K):
    x,y = map(int,input().split())
    if(d[x] == d[y]):
        b[x].append(y)
        b[y].append(x)

c = Counter(d)
for i in range(1,N+1):
    print(c[d[i]] - len(f[i]) - len(b[i])-1)

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())
uf = UnionFind(n)
dame = [set() for _ in range(n)]

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

for i 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):
    ans = uf.size(i) - 1
    ans -= len(dame[i])
    print(ans, end=" ")

Solution (Python):
import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        
        
        self.par = [-1] * n
        
        self.size = [1] * n

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

    def 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
        self.par[y]=x
        self.size[x]+=self.size[y]

import sys
input=sys.stdin.readline
n,m,k=map(int,input().split())
uf=UnionFind(n)
out=[[] for i in range(n)]

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

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

for i in range(n):
    ans=uf.size[uf.find(i)]-1-len(out[i])
    print(ans,end=' ')

Solution (Python):
import sys
from collections import defaultdict, deque
 
readline = sys.stdin.readline
n, m, k = map(int, readline().split())


 
friend = [set() for i in range(n)]
not_friend = [set() for i in range(n)]
 
suggest_friends = [-1] * n
for i in range(m):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    friend[a].add(b)
    friend[b].add(a)
    
for i in range(k):
    c, d = map(int, readline().split())
    c -= 1
    d -= 1
    not_friend[c].add(d)
    not_friend[d].add(c)
    
for i in range(n):
    if suggest_friends[i] != -1:
        continue
    q = deque(friend[i])
    friend_group = set(friend[i])
    while q:
        p = q.popleft()
        for f in friend[p]:
            if not(f in friend_group):
                q.append(f)
                friend_group.add(f)
    num = len(friend_group)
    for f in friend_group:
        suggest_friends[f] = num - 1 - len(friend[f] | not_friend[f] & friend_group)
 
for i in range(n):
    if suggest_friends[i] == -1:
        suggest_friends[i] = 0
print(*suggest_friends)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
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()
A = [LIST() for i in range(M)]
C = [LIST() for i in range(K)]

tree = UnionFind(N)
block = defaultdict(list)
friend = defaultdict(list)

for a, b in A:
    tree.union(a-1, b-1)
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)

for c, d in C:
    block[c-1].append(d-1)
    block[d-1].append(c-1)

for i in range(N):
    block_num = 0
    for b in block[i]:
        
        if tree.same(i, b):
            block_num += 1

    ans = tree.size(i) - 1 - len(friend[i]) - block_num
    print(ans, end=" ")
print()

Solution (Python):
n,m,k=map(int,input().split())
def root(x):
    while par[x]>=0:x=par[x]
    return x
def unite(x,y):
    x,y=root(x),root(y)
    if x!=y:
        if x>y:x,y=y,x
        par[x]+=par[y]
        par[y]=x
par=[-1]*n
def same(x,y):
    return root(x)==root(y)
def size(x):
  return-par[root(x)]
g=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    unite(a,b)
    g[a].append(b)
    g[b].append(a)
ss=[size(i)-len(g[i])-1 for i in range(n)]
for  i in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    if same(c,d):
        ss[c]-=1
        ss[d]-=1
print(*ss)