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):
class UnionFind:
    """
    parents: 各要素の親要素
             要素がrootの場合には　-(そのグループに属する要素数) を格納
    """
    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())

union_find = UnionFind(n)
friends_counter = {i: 0 for i in range(n)}
blocks_counter = {i: 0 for i in range(n)}

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

for _ in range(k):
    c, d = map(int, input().split())
    if union_find.same(c-1, d-1):
        blocks_counter[c-1] += 1
        blocks_counter[d-1] += 1

result = []
for i in range(n):
    result.append(str(union_find.size(i) - friends_counter[i] - blocks_counter[i] - 1))

print(" ".join(result))

Solution (Python):
N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


group = {i: -1 for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
for i in range(1, N + 1):
    if group[i] >= 0:
        continue
    queue = [i]
    group[i] = i
    count[i] += 1
    while queue:
        new = []
        for cur in queue:
            for nxt in graph[cur]:
                if group[nxt] == -1:
                    group[nxt] = group[cur]
                    count[group[nxt]] += 1
                    new.append(nxt)
        queue = new

res = [0] * N

for i in range(N):
    res[i] = count[group[i + 1]] - 1


for i in range(N):
    for j in banned[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
    for j in graph[i + 1]:
        if group[i + 1] == group[j]:
            res[i] -= 1
print(*res)

Solution (Python):
from collections import defaultdict


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

    def root(self, A):
        
        
        
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  

        if self.size(A) < self.size(B):
            
            
            A, B = B, A

        
        self.parent[A] += self.parent[B]
        
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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


uf = UnionFind(N)


frd = defaultdict(int)

blk = [[] for _ in range(N)]  
ans = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frd[a] += 1
    frd[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blk[a].append(b)
    blk[b].append(a)
for i in range(N):
    ans[i] = uf.size(i) - 1 - frd[i]
    for j in blk[i]:
        if uf.same(i, j):
            ans[i] -= 1  
print(*ans)

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

    def root(self, A):
        
        
        
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  

        if self.size(A) < self.size(B):
            
            
            A, B = B, A

        
        self.parent[A] += self.parent[B]
        
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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


uf = UnionFind(N)
frd = [0] * N  
blk = [[] for _ in range(N)]  
ans = [0] * N

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    frd[a] += 1
    frd[b] += 1
    uf.unite(a, b)
for i in range(K):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    blk[a].append(b)
    blk[b].append(a)
for i in range(N):
    ans[i] = uf.size(i) - 1 - frd[i]
    for j in blk[i]:
        if uf.same(i, j):
            ans[i] -= 1 
print(*ans)

Solution (Python):
import sys

sys.setrecursionlimit(6500)

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
d=[-1]*N

def find(n):
    if d[n]<0:
        return n
    else:
        d[n]=find(d[n])
        return d[n]
def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def same(a,b):
    if find(a)==find(b):return True
    else:return False


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

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

ans=[0]*N
for i in range(N):
    p=find(i)
    ans[i]=-d[p]-len(F[i])-1
    for b in B[i]:
        if same(i,b):
            ans[i]-=1
for i in ans:
    print(str(i),end=" ")

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        return -self.parent[self.root(x)]

n, m, k = map(int, input().split())
friends = [ [] for _ in range(n) ]
blocks  = [ [] for _ in range(n) ]

tree = UnionFind(n)

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

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

for i in range(n):
    ret = tree.size(i)
    s = set()
    for j in friends[i]:
        s.add(j)
    for j in blocks[i]:
        if tree.same(i, j):
            s.add(j)
    ret -= len(s)
    print(ret-1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    def size(self, x):
        return -self.parent[self.root(x)]

n, m, k = map(int, input().split())
friends = [ [] for _ in range(n) ]
blocks  = [ [] for _ in range(n) ]

tree = UnionFind(n)

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

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

for i in range(n):
    ret = tree.size(i)
    s = set()
    for j in friends[i]:
        s.add(j)
    for j in blocks[i]:
        if tree.same(i, j):
            s.add(j)
    ret -= len(s)
    print(ret-1)

Solution (Python):
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

f = [set() for _ in range(N+1)]
b = [set() for _ in range(N+1)]

for i,j in friend:
    f[i].add(j)
    f[j].add(i)
for i,j in block:
    b[i].add(j)
    b[j].add(i)

stack=deque()
ans = [0]*(N+1)
visited = [0]*(N+1)

for i in range(1,N+1):
    if visited[i]:
        continue
    link = {i}
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in f[n]:
            if visited[j]==0:
                stack.append(j)
                visited[j] = 1
                link.add(j)
    for i in link:
        ans[i] = len(link) - len(link & f[i]) - len(link & b[i]) - 1
print(*ans[1:])

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

class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n)]
    
    def find_root(self, n):
        if self.par[n] < 0:
            return n
        else:
            self.par[n] = self.find_root(self.par[n])
            return self.par[n]

    def union(self, n_1, n_2):
        par_1 = self.find_root(n_1)
        par_2 = self.find_root(n_2)
        if par_1 == par_2:
            return
        else:
            if self.par[par_1] <= self.par[par_2]:
                self.par[par_1] += self.par[par_2]
                self.par[par_2] = par_1
            else:
                self.par[par_2] += self.par[par_1]
                self.par[par_1] = par_2

if __name__ == "__main__":
    ans = []
    unionfind = UnionFind(N)
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a_i, b_i = map(int, input().split())
        a_i -= 1
        b_i -= 1
        unionfind.union(a_i, b_i)
        friend[a_i].append(b_i)
        friend[b_i].append(a_i)
    block = [[] for _ in range(N)]
    for i in range(K):
        c_i, d_i = map(int, input().split())
        c_i -= 1
        d_i -= 1
        block[c_i].append(d_i)
        block[d_i].append(c_i)
    for i in range(N):
        block_sum = 0
        for block_user in block[i]:
            if unionfind.find_root(i) == unionfind.find_root(block_user):
                block_sum += 1
        ans.append(str(unionfind.par[unionfind.find_root(i)] * -1 -1 - len(friend[i]) - block_sum))
        
    print(" ".join(ans))

Solution (Python):
N,M,K = map(int,input().split())
Fri = [list(map(int,input().split())) for _ in range(M)]
Blo = [list(map(int,input().split())) for _ in range(K)]


par = [i for i in range(N+1)]
relation = [1 for _ in range(N+1)] 
rank = [0 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

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

ans = [relation[find(i)] for i in range(N+1)]
for m in range(M):
    unite(Fri[m][0],Fri[m][1])
    ans[Fri[m][0]] -= 1
    ans[Fri[m][1]] -= 1

for k in range(K):
    if same(Blo[k][0],Blo[k][1]):
        ans[Blo[k][0]] -= 1
        ans[Blo[k][1]] -= 1

for i in range(1,N+1):
    ans[i] += (relation[find(i)] - 2)
    if i != 1:
        print(" ",end="")
    print(ans[i],end="")

Solution (Python):
import sys

sys.setrecursionlimit(6500)

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]
d=[-1]*N

def find(n):
    if d[n]<0:
        return n
    else:
        return find(d[n])
def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:return False
    if d[a]<=d[b]:
        d[a]+=d[b]
        d[b]=a
    else:
        d[b]+=d[a]
        d[a]=b
    return True

def same(a,b):
    if find(a)==find(b):return True
    else:return False


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

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

ans=[0]*N
for i in range(N):
    p=find(i)
    ans[i]=-d[p]-len(F[i])-1
    for b in B[i]:
        if same(i,b):
            ans[i]-=1
for i in ans:
    print(str(i),end=" ")

Solution (Python):
import sys
sys.setrecursionlimit(4100000)

class Uf():
    def __init__(self, n):
        self.par = [-1]*N
 
    def root(self, x):
        if self.par[x] < 0:
            return x
        
        root_x = self.root(self.par[x])
        self.par[x] = root_x
        return root_x
    
    def merge(self, a, b):
        a, b = self.root(a), self.root(b)
        
        if a == b:
            return
            
        if self.par[a] > self.par[b]:
            a, b = b, a
        
        self.par[a] += self.par[b]
        self.par[b] = a
                 
    def isSame(self, a, b):
        return self.root(a) == self.root(b)
    
    def size(self, x):
        return -self.par[self.root(x)]


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

exep = [[] for i in range(N)]

uf = Uf(N)

for i in range(M):
    a, b  = map(int,input().split())
    a, b = a-1, b-1 
    exep[a].append(b)
    exep[b].append(a)
    uf.merge(a, b)

for i in  range(K):
    a, b  = map(int,input().split())
    a, b = a-1, b-1
    if not uf.isSame(a,b):
        continue
    exep[a].append(b)
    exep[b].append(a)

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

Solution (Python):
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)]

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

u=UnionFind(n)
for i in range(m):
    a,b=ab[i]
    u.Unite(a,b)
l=[u.Count(i)-1 for i in range(n+1)]
for i in range(m):
    a,b=ab[i]
    l[a]-=1
    l[b]-=1
for i in range(k):
    c,d=cd[i]
    if u.isSameGroup(c,d):
        l[c]-=1
        l[d]-=1
print(*l[1:])

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

    N, M, K=map(int, input().split())
    friend_or_block = [list() for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.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):
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [set() for _ in range(N)]
    friends_chain = UnionFindTree(N)

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

    for _ in range(K):
        c, d = map(int, input().split())
        c, d = c-1, d-1
        if friends_chain.same(c, d):
            friend_or_block[c].add(d)
            friend_or_block[d].add(c)

    print(*[friends_chain.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):
import sys
def main():
    input = sys.stdin.readline

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - 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):
import sys
def main():
    input = sys.stdin.readline
    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)]

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.size(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    class UnionFindTree:
        def __init__(self, n):
            self.parent = [-1] * n

        def root(self, x):
            p, s = self.parent[x], list()
            while p >= 0:
                s.append(x)
                x, p = p, self.parent[p]
            for c in s: self.parent[c] = x
            return x

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

        def count(self, x): return -self.parent[self.root(x)]

        def unite(self, x, y):
            xr, yr = self.root(x), self.root(y)
            if xr == yr: return
            if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
            self.parent[xr] += self.parent[yr]
            self.parent[yr] = xr

    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    friends_chain = UnionFindTree(N)

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

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

    print(*[friends_chain.count(i) - friend_or_block[i] - 1 for i in range(N)])

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

    def root(self, x):
        p, s = self.parent[x], list()
        while p >= 0:
            s.append(x)
            x, p = p, self.parent[p]
        for c in s: self.parent[c] = x
        return x

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

    def count(self, x): return -self.parent[self.root(x)]

    def unite(self, x, y):
        xr, yr = self.root(x), self.root(y)
        if xr == yr: return
        if self.parent[xr] > self.parent[yr]: xr, yr = yr, xr
        self.parent[xr] += self.parent[yr]
        self.parent[yr] = xr

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - len(frd[i]) - 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

Solution (Python):
from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")

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

par = [-1 for _ in range(n)]

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

def union(x, y):
    x, y = find(x), find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

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

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

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

for j in range(k):
    c, d = map(int, input().split())
    if same(c-1, d-1):
        ans[c-1] -=1
        ans[d-1] -=1

for i in range(n):
    ans[i] += size(i)

print(*ans)

Solution (Python):


import sys
readline = sys.stdin.readline

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

F = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, readline().split())
    F[a].append(b)
    F[b].append(a)

B = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, readline().split())
    B[c].append(d)
    B[d].append(c)

seen = [-1] * (N + 1)
group = 0


def dfs(graph, s):
    stack = [s]
    seen[s] = group
    n_connection = 1

    while stack:
        u = stack.pop()
        for v in graph[u]:
            if seen[v] == -1:
                n_connection += 1
                seen[v] = group
                stack.append(v)

    return n_connection


union = {}
for i in range(1, N + 1):
    if seen[i] == -1:
        n = dfs(F, i)
        union[group] = n
        group += 1

ans = []
for i in range(1, N + 1):
    tmp = 0
    tmp += union[seen[i]] - 1
    tmp -= len(F[i])
    for j in B[i]:
        if seen[j] == seen[i]:
            tmp -= 1
    ans.append(tmp)

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

Solution (Python):
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=p[:]
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=y=x
 if x==y:s[a]-=1;s[b]-=1;m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

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

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

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]


def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]

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

def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

ans = [0 for _ in range(N)]

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(' '.join(map(str, ans)))

Solution (Python):
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=p[:]
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=y=x
 if x==y:s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])

Solution (Python):
r=lambda x:p[x]>0and r(p[x])or x
(n,m,k),*t=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
s=[-1]*-~n
for a,b in t:
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>0:p[x]+=p[y];p[y]=x
 if(x==y)+(m>0):s[a]-=1;s[b]-=1
 m-=1
print(*[s[i+1]-p[r(i+1)]for i in range(n)])