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 itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60


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



a = [0] * m
b = [0] * m
c = [0] * k
d = [0] * k
for i in range(m + k):
    x, y = map(int, input().split())
    if i < m:
        a[i] = x - 1
        b[i] = y - 1
        uf.union(x - 1, y - 1)
    else:
        c[i - m] = x - 1
        d[i - m] = y - 1
e = [set() for i in range(n)]
for i in range(m):
    if uf.same(a[i], b[i]):
        e[a[i]].add(b[i])
        e[b[i]].add(a[i])
for i in range(k):
    
    
    if uf.same(c[i], d[i]):
        e[c[i]].add(d[i])
        e[d[i]].add(c[i])


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

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n+1))
        self.size = [1] * (n+1)
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if self.parent[a] == self.parent[b]:
            return
        if self.size[a] >= self.size[b]:
            self.parent[b] = a
            self.size[a] += self.size[b]
        else:
            self.parent[a] = b
            self.size[b] += self.size[a]
        
    def is_same(self, a, b):
        return self.find(a) == self.find(b)
    
    def count(self, x):        
        return self.size[self.find(x)]

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

uf = UnionFind(n)
ans = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for _ in range(k):
    a, b = map(int, input().split())
    if uf.is_same(a, b):
        ans[a] -= 1
        ans[b] -= 1
        
for i in range(1, n+1):
    ans[i] += uf.count(i) - 1    
    
print(" ".join(map(str, ans[1:])))

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n+1))
        self.size = [1] * (n+1)
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        
        if self.parent[a] == self.parent[b]:
            return
        if self.size[a] >= self.size[b]:
            self.parent[b] = a
            self.size[a] += self.size[b]
        else:
            self.parent[a] = b
            self.size[b] += self.size[a]
        
    def count(self, x):        
        return self.size[self.find(x)]

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

uf = UnionFind(n)
ans = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for _ in range(k):
    a, b = map(int, input().split())
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1
        
for i in range(1, n+1):
    ans[i] += uf.count(i) - 1    
    
print(" ".join(map(str, ans[1:])))

Solution (Python):
class UnionFind:
    def __init__(self, N, l):
        self.roots = list(range(N+1))
        self.counter = [1]*(N+1)
        for a, b in l:
            self.union(a, b)

    def get_root(self, n):
        if self.roots[n] != n:
            self.roots[n] = self.get_root(self.roots[n])
        return self.roots[n]

    def union(self, a, b):
        a, b = sorted([self.get_root(a), self.get_root(b)])
        if a != b:
            self.roots[b] = a
            self.counter[a] += self.counter[b]
            self.counter[b] = 0

    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)

    def count(self, x):
        return(self.counter[self.get_root(x)])


N, M, K = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(M)]
cd = [[int(i) for i in input().split()] for _ in range(K)]
friend = [[] for _ in range(N+1)]
uf = UnionFind(N, ab)

for a, b in ab:
    friend[a].append(b)
    friend[b].append(a)

ans = [uf.count(i)-1-len(friend[i]) for i in range(N+1)]

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

print(*ans[1:])

Solution (Python):
class UnionFind:
    __slots__ = ["_size", "_first_idx", "_parents"]

    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)

    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]
n,m,k=map(int,input().split())
from sys import stdin 
input=stdin.readline
friend=[0]*(n+1)
uf=UnionFind(n,1)
for i in range(m):
    a,s=map(int,input().split())
    uf.unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n+1)]
for i in range(k):
    a,b=map(int,input().split())
    anti[a].add(b)
    anti[b].add(a)
print(*[uf.size(i)-1-sum(uf.same(i,b) for b in anti[i])-friend[i] for i in range(1,n+1)],sep=" ")

Solution (Python):
n,m,k=map(int,input().split())
par=[-1]*n


def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    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 size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)
from sys import stdin 
input=stdin.readline
friend=[0]*n
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a]+=1
    friend[s]+=1
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)

print(*[size(i)-1-sum(same(i,b) for b in anti[i])-friend[i] for i in range(n)],sep=" ")

Solution (Python):
n,m,k = map(int,input().split())
a = [0]*m
b = [0]*m
c = [0]*k
d = [0]*k
for i in range(m):
    a[i],b[i] = map(int,input().split())
for i in range(k):
    c[i],d[i] = map(int,input().split())

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    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.par[y] += self.par[x] 
            self.par[x] = y
        else:
            self.par[x] += self.par[y]
            self.par[y] = x
            if self.rank[x] == self.rank[y]: 
                self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

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

friend = [[]*(n+1) for i in range(n+1)]
for i in range(m):
    friend[a[i]].append(b[i])

block = [[]*(n+1) for i in range(n+1)]
for i in range(k):
    block[c[i]].append(d[i])
    block[d[i]].append(c[i])

Tree = UnionFind(n)

for i in range(1,len(friend)):
    for j in friend[i]:
        Tree.union(i-1,j-1)

for i in range(m):
    friend[b[i]].append(a[i])

ans = [0]*n

for i in range(n):
    s = Tree.size(i)
    s -= len(friend[i+1]) 
    for j in block[i+1]:
        if Tree.is_same(i,j-1): 
            s -= 1

    ans[i] = s-1

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, k = map(int, input().split())

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

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

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

        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

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

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)
ab = []
cd = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

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

ans = [uf.count_member(i)-1 for i in range(n)]

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

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

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m, k = map(int, input().split())


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

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

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

        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

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

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)
ab = []
cd = []

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

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

ans = [uf.count_member(i)-1 for i in range(n)]

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

for c, d in cd:
    if uf.same(c, d):
        ans[c] -= 1
        ans[d] -= 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)]
B=[0]*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)
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
L=[]
for i in range(n):
      L.append(uf.size(i)-1-len(F[i])+B[i])
print(*L)

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):
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, y = self.find_root(x), self.find_root(y)
        if(x == y):
            return
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
    def __str__(self):
        return 'UnionFind(n: {}, root: {}, rnk: {})'.format(self.n, self.root, self.rnk)
    
    def __repr__(self):
        return self.__str__()

inputs = open(0).readlines()
n, m, k = map(int, inputs[0].split())
AB = [tuple(map(int, ab.split())) for ab in inputs[1:m+1]]
CD = [tuple(map(int, cd.split())) for cd in inputs[m+1:]]

uf = UnionFind(n)
friends = [set() for _ in range(n)]
for n0, n1 in AB:
    uf.unite(n0-1, n1-1)
    friends[n0-1].add(n1-1)
    friends[n1-1].add(n0-1)

blocks = [set() for _ in range(n)]
for n0, n1 in CD:
    if uf.is_same_group(n0-1, n1-1):
        blocks[n0-1].add(n1-1)
        blocks[n1-1].add(n0-1)

candidates = []
for i in range(n):
    candidates.append(uf.count(i) - len(friends[i]) - len(blocks[i]) - 1)
print(*candidates)

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())
F=[set()for _ in range(n)]
uf=UF(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
ans=[]
for i in range(n):
      ans.append(uf.size(i)+B[i]-1-len(F[i]))
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()}

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

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    if uf.same(c, d):
        block[c].append(d)
        block[d].append(c)
ans = [0] * N
for i in range(N):
    ans[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1
print(*ans)

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.par = []
        self.size = []
        for i in range(n):
            self.par.append(i)
            self.size.append(1)

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

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

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

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

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

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

answer = []
for i in range(n):
    ans = uf.root_size(i)-len(non[i])-1
    answer.append(ans)

print(*answer)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

N,M,K=LI()
UF=UnionFindTree(N)
NUMF = [0]*(N+1)
for i in range(M):
    f,t = LI()
    UF.unite(f,t)
    NUMF[f] += 1
    NUMF[t] += 1

BLL=[]
for j in range(K):
    f, t = LI()
    BLL.append((f,t))
    BLL.append((t,f))
BLL.sort()
GPS = [0]*(N+1)

for i in range(1, N+1):
    UF.find(i)
    GPS[UF.nodes[i]] += 1

ptr = 0
K2 = 2*K
for i in range(1, N+1):
    res = GPS[UF.find(i)] - 1 - NUMF[i]
    while BLL and ptr < K2 and i == BLL[ptr][0]:
        res -= UF.is_same(BLL[ptr][0], BLL[ptr][1])
        ptr += 1
    print(res, end=" ")
print("")

Solution (Python):










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



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

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

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

        if x == y:
            return

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

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

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

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

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

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

w = [0] * n
for i in range(n):
    w[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1

print(*w)

Solution (Python):



from collections import deque






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



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

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

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

        if x == y:
            return

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

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

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

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

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

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

w = [0] * n
for i in range(n):
    w[i] = uf.size(i) - len(friend[i]) - len(block[i]) - 1

print(*w)

Solution (Python):

import collections


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

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

    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

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


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

friend_cnt = [0] * n
blocked_cnt = [0] * n

uf = UnionFind(n)

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

for i in range(k):
    c, d = map(int, input().split())
    if uf.isSameGroup(c-1, d-1):
        blocked_cnt[c-1] = blocked_cnt[c-1] + 1
        blocked_cnt[d-1] = blocked_cnt[d-1] + 1

for i in range(n):
    renketsu_cnt_i = uf.Count(i)
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - friend_cnt[i] - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        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 same(self, x, y):
        return self.find(x) == self.find(y)

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
deg = [0 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    deg[a - 1] += 1
    deg[b - 1] += 1
    uf.union(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.size(i) - 1 - deg[i]
    for u in block[i]:
        if uf.same(i, u):
            res -= 1
    ans.append(res)

print(*ans)

Solution (Python):
import sys 
sys.setrecursionlimit(500*500) 

class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.size = [1] * n
    def find(self, x):
        if self.parent[x] == -1:
            return x
        else:
            a = self.find(self.parent[x])
            self.parent[x] = a
            return a
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parent[x] = y
            self.size[y] += self.size[x]
    def get_size(self, x):
        return self.size[self.find(x)]
    def printout(self):
        print(self.parent)
        print(self.size)

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

ab = [[int(i)-1 for i in input().split()] for j in range(M)]
cd = [[int(i)-1 for i in input().split()] for j in range(K)]

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

ans =[uf.get_size(i)-1 for i in range(N)]

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

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

print(*ans)

Solution (Python):
n,m,k = map(int,input().split())
cut = [[] for i in range(n)]

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

def find(x, par):
    if x == par[x]:
        return x
    else:
        x = par[x]
        return find(x, par)
def unite(x, y, par, rank, size):
    x = find(x, par)
    y = find(y, par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a, b, par, rank, size)
    cut[a].append(b)
    cut[b].append(a)
for i in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    if find(c, par) == find(d, par):
        cut[c].append(d)
        cut[d].append(c)
ans = []
for i in range(n):
    ans.append(size[find(i,par)]-len(cut[i])-1)
print(' '.join(map(str,ans)))