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:

    def __init__(self,n):
        self.uf = [-1]*n

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

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

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

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

ans = [un.size(i)-fre[i] for i in range(n)]

for i in range(k):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if un.same(a,b):
        ans[a] -= 1
        ans[b] -= 1
print(*ans)

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32





class UnionFind:
    def __init__(self, n):
        
        self.par = [-1] * (n+1)
        
        self.rank = [0] * (n+1)
    
    
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

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

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

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

        
        if(x == y):
            return False

        
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        
        self.par[x] += self.par[y]
        
        self.par[y] = x

        return True 
    
    def root_nodes(self):
        return len([i for i in self.par[1:] if i <= -1])
    
    

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    """graph.input.linkedlist
        input: u[]:start, v[]:end
        output:g[][]
    """
    uf = UnionFind(N)

    g = [[] for i in range(N+1)]
    for i in range(M):
        g[A[i]].append(B[i])
        g[B[i]].append(A[i])
    
    g_b = [[] for i in range(N+1)]
    for i in range(K):
        g_b[C[i]].append(D[i])
        g_b[D[i]].append(C[i])
    

    for i in range(M):
        uf.union(A[i], B[i])

    ans = []
    for i in range(1, N+1):
        ans.append(uf.size(i)-1 - len(g[i]) - len([x for x in g_b[i] if uf.same_check(i, x) == True]))
        
    print(' '.join(map(str, ans)))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  
    D = [int()] * (K)  
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32





class UnionFind:
    def __init__(self, n):
        
        self.par = [-1] * (n+1)
        
        self.rank = [0] * (n+1)
    
    
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

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

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

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

        
        if(x == y):
            return False

        
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        
        self.par[x] += self.par[y]
        
        self.par[y] = x

        return True 
    
    def root_nodes(self):
        return len([i for i in self.par[1:] if i <= -1])
    
    

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    """graph.input.linkedlist
        input: u[]:start, v[]:end
        output:g[][]
    """
    uf = UnionFind(N)

    g = [[] for i in range(N+1)]
    for i in range(M):
        g[A[i]].append(B[i])
        g[B[i]].append(A[i])
    
    g_b = [[] for i in range(N+1)]
    for i in range(K):
        g_b[C[i]].append(D[i])
        g_b[D[i]].append(C[i])
    

    for i in range(M):
        uf.union(A[i], B[i])

    
    

    
    
    ans = []
    for i in range(1, N+1):
        
        ans.append(uf.size(i)-1 - len(g[i]) - len([x for x in g_b[i] if uf.same_check(i, x) == True]))
        
    print(' '.join(map(str, ans)))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    K = int(next(tokens))  
    A = [int()] * (M)  
    B = [int()] * (M)  
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  
    D = [int()] * (K)  
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind():
    def __init__(self, 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
n,m,k = map(int,input().split())
uf = UnionFind(n)

friend = [0]*n

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

block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

Solution (Python):

class UnionFind():
    def __init__(self, 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
n,m,k = map(int,input().split())
uf = UnionFind(n)

friend = [0]*n

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

block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

Solution (Python):
import sys
from bisect import bisect_left,bisect_right,insort
input = sys.stdin.readline
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 unite(self,x,y):
    
    
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        else:
            if self.size[x]>=self.size[y]:
                self.parent[y]=x
                self.size[x]+=self.size[y]
            else:
                self.parent[x]=y
                self.size[y]+=self.size[x]
    def cnt(self,x):
    
        return self.size[self.find(x)]

def main():
    n,m,k=map(int,input().split())
    u=UnionFind(n)
    ans=[0]*(n+1)
    for i in range(m):
        a,b=map(int,input().split())
        ans[a]-=1
        ans[b]-=1
        u.unite(a,b)
    for i in range(k):
        a,b=map(int,input().split())
        if u.find(a)==u.find(b):
            ans[a]-=1
            ans[b]-=1
    for i in range(1,n+1):
        ans[i]+=u.cnt(i)-1
    print(" ".join(map(str,ans[1:])))

if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind():
    def __init__(self, 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
n,m,k = map(int,input().split())
uf = UnionFind(n)

friend = [0]*n

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

block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

Solution (Python):

class UnionFind():
    
    def __init__(self, n):  
        self.parent = [None] * n 
        self.rank = [None] * n   
        self._size = [1] * n 
        for i in range(n):
            self.parent[i] = i
            self.rank[i] = 0

    
    def root_of(self, x):
        children = [x]
        while self.parent[x] != x:
            x = self.parent[x]
            children.append(x)

        for ch in children:
            self.parent[ch] = x

        return x

    
    def unite(self, x, y):
        rx = self.root_of(x)
        ry = self.root_of(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]: 
            self.parent[rx] = ry  
            self._size[ry] += self._size[rx]
        else:
            self.parent[ry] = rx
            self._size[rx] += self._size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    
    def is_same(self, x, y):
        return self.root_of(x) == self.root_of(y)

    
    def size(self, x):
        return self._size[self.root_of(x)]



N, M, K = [int(x) for x in input().split()]

Ef = [[int(x) - 1 for x in input().split()] for _ in range(M)]
Eb = [[int(x) - 1 for x in input().split()] for _ in range(K)]

ans = [0] * N
uf = UnionFind(N)
for i in range(M):
    uf.unite(Ef[i][0], Ef[i][1])
    ans[Ef[i][0]] -= 1  
    ans[Ef[i][1]] -= 1

for i in range(K):
    if uf.is_same(Eb[i][0], Eb[i][1]):
        ans[Eb[i][0]] -= 1  
        ans[Eb[i][1]] -= 1

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

print(" ".join([str(i) for i in ans]))

Solution (Python):
class union_find():
    __slots__ = ["par", "rank", "size"]
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]
        self.size = [1 for i in range(n + 1)]

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

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):

        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
            self.size[yr] += self.size[xr]
        else:
            self.par[yr] = xr
            self.size[xr] += self.size[yr]
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def size_belong(self, i):
        return self.size[self.find(i)]

    def mass_size(self):
        return [i == v for i, v in enumerate(self.par)].count(True) - 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

def main():
    from collections import defaultdict

    dicf = defaultdict(lambda :[])
    dicb = defaultdict(lambda :[])

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

    uf = union_find(N)
    for i in range(M):
        a, b = map(int, input().split())
        dicf[a].append(b)
        dicf[b].append(a)
        if a > b:
            a, b = b, a
        uf.union(a, b)

    for i in range(K):
        c, d = map(int, input().split())
        dicb[c].append(d)
        dicb[d].append(c)

    ans = []
    for i in range(1, N + 1):
        x = uf.size_belong(i) - len(dicf[i]) - 1
        m = 0
        for b in dicb[i]:
            if uf.find(b) == uf.find(i):
                m += 1

        ans.append(x - m)


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




if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind():
    
    def __init__(self, n):  
        self.parent = [None] * n 
        self.rank = [None] * n   
        self._size = [1] * n 
        for i in range(n):
            self.parent[i] = i
            self.rank[i] = 0

    
    def root_of(self, x):
        children = [x]
        while self.parent[x] != x:
            x = self.parent[x]
            children.append(x)

        for ch in children:
            self.parent[ch] = x

        return x

    
    def unite(self, x, y):
        rx = self.root_of(x)
        ry = self.root_of(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]: 
            self.parent[rx] = ry  
            self._size[ry] += self._size[rx]
        else:
            self.parent[ry] = rx
            self._size[rx] += self._size[ry]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    
    def is_same(self, x, y):
        return self.root_of(x) == self.root_of(y)

    
    def size(self, x):
        return self._size[self.root_of(x)]



N, M, K = [int(x) for x in input().split()]

Ef = [[int(x) - 1 for x in input().split()] for _ in range(M)]
Eb = [[int(x) - 1 for x in input().split()] for _ in range(K)]

ans = [0] * N
uf = UnionFind(N)
for i in range(M):
    uf.unite(Ef[i][0], Ef[i][1])
    ans[Ef[i][0]] -= 1  
    ans[Ef[i][1]] -= 1

for i in range(K):
    if uf.is_same(Eb[i][0], Eb[i][1]):
        ans[Eb[i][0]] -= 1  
        ans[Eb[i][1]] -= 1

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

print(" ".join([str(i) for i in ans]))

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

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

    g = tuple(set() for _ in range(N))
    direct_friend = [0] * N
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())

        g[a].add(b)
        g[b].add(a)

        direct_friend[a] += 1
        direct_friend[b] += 1

    bk = tuple(set() for _ in range(N))
    for _ in range(K):
        c, d = (int(x) - 1 for x in input().split())
        bk[c].add(d)
        bk[d].add(c)

    dq = deque()
    checked = [-1] * N
    for v in range(N):
        if ~checked[v]: continue

        dq.append(v)  
        checked[v] = v
        root = v
        while dq:
            v = dq.pop()
            for u in g[v]:
                if ~checked[u]: continue
                checked[u] = root
                dq.append(u)

    ctr = [0] * N
    for v in range(N):
        root = checked[v]
        ctr[root] += 1

    ret = []
    for v in range(N):
        root = checked[v]
        t = ctr[root] - direct_friend[v] - 1 - sum(checked[u] == root for u in bk[v])
        ret.append(t)

    print(*ret)


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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    N, M, K = map(int, input().split())
    dame = [set() for i in range(N)]
    uf = UnionFind(N)

    for i in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        
        dame[a].add(b)
        dame[b].add(a)
        uf.unite(a,b)
    
    for i in range(K):
        c, d = map(lambda x: int(x)-1, input().split())
        if not uf.isSame(c, d):
            continue
        dame[c].add(d)
        dame[d].add(c)
    
    ans = []
    for i in range(N):
        mem = uf.size(i) - 1
        mem -= len(dame[i])
        ans.append(mem)
    
    print(*ans, sep=' ')

if __name__ == '__main__':
    solve()

Solution (Python):
def main():
    from collections import defaultdict, deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    direct_friend = [0] * N
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())

        g[a].add(b)
        g[b].add(a)

        direct_friend[a] += 1
        direct_friend[b] += 1

    bk = tuple(set() for _ in range(N))
    for _ in range(K):
        c, d = (int(x) - 1 for x in input().split())
        bk[c].add(d)
        bk[d].add(c)

    dq = deque()
    checked = [-1] * N
    for v in range(N):
        if ~checked[v]: continue

        dq.append(v)  
        checked[v] = v
        root = v
        while dq:
            v = dq.pop()
            for u in g[v]:
                if ~checked[u]: continue
                checked[u] = root
                dq.append(u)

    ctr = defaultdict(int)
    for v in range(N):
        root = checked[v]
        ctr[root] += 1

    ret = []
    for v in range(N):
        root = checked[v]
        t = ctr[root] - direct_friend[v] - 1 - sum(checked[u] == root for u in bk[v])
        ret.append(t)

    print(*ret)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import defaultdict, deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    direct_friend = [0] * N
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())

        g[a].add(b)
        g[b].add(a)

        direct_friend[a] += 1
        direct_friend[b] += 1

    bk = tuple(set() for _ in range(N))
    for _ in range(K):
        c, d = (int(x) - 1 for x in input().split())
        bk[c].add(d)
        bk[d].add(c)

    dq = deque()
    checked = [-1] * N
    for v in range(N):
        if ~checked[v]:
            continue

        dq.append((v, v))  
        checked[v] = v
        while dq:
            v, root = dq.pop()
            for u in g[v]:
                if ~checked[u]:
                    continue
                checked[u] = root
                dq.append((u, root))

    ctr = defaultdict(int)
    for v in range(N):
        root = checked[v]
        ctr[root] += 1

    ret = []
    for v in range(N):
        root = checked[v]
        t = ctr[root] - direct_friend[v] - 1
        for u in bk[v]:
            if checked[u] == root:
                
                
                t -= 1
        ret.append(t)

    print(*ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

def main():
    N,M,K=mis()
    uf = UnionFindEx(N)
    frs = tuple(set() for _ in range(N))
    bls = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = mis()
        uf.connect(a-1, b-1)
        frs[a-1].add(b-1)
        frs[b-1].add(a-1)
    for _ in range(K):
        a, b = mis()
        bls[a-1].add(b-1)
        bls[b-1].add(a-1)
    for i in range(N):
        print(uf.getGroupSize(i) - len(frs[i]) - sum(uf.getRootID(i)==uf.getRootID(k) for k in bls[i]) - 1, end=' ')


main()

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

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

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


D = {}
parent = [-1] * N
visited = [False] * N
for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    stack = [root]
    while stack:
        n = stack.pop()
        visited[n] = True
        parent[n] = root

        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    group = D[parent[iam]]
    tmp_ans = len(group) - len(F[iam]) - 1
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

Solution (Python):
from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
G = [[] for _ in range(N)]
deg = [0 for _ in range(N)]
reds = [[] for _ in range(N)]

for _ in range(M):
    _a, _b = list(map(int, input().split()))
    _a -= 1
    _b -= 1
    G[_a].append(_b)
    G[_b].append(_a)
    deg[_a] += 1
    deg[_b] += 1



numbers = {i: None for i in range(N)}

def dfs():
    visited = [False for _ in range(N)]
    stack = []
    for i in range(N):
        if not visited[i]:
            stack.append(i)
            while len(stack) > 0:
                v = stack.pop()
                visited[v] = True
                numbers[v] = i
                for neighbor in G[v]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
dfs()

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    _c -= 1
    _d -= 1
    if numbers[_c] == numbers[_d]:
        reds[_c].append(_d)
        reds[_d].append(_c)

counter = {}
for i in range(N):
    if numbers[i] not in counter:
        counter[numbers[i]] = 1
    else:
        counter[numbers[i]] += 1

for i in range(N):
    v = counter[numbers[i]] - len(G[i]) - len(reds[i]) - 1
    print(v, end='')
    if i < N - 1:
        print(" ", end='')
print()

Solution (Python):
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline

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

    fre = [[] for i in range(n)]

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

    group = [-1]*n
    def check():
        dic = {}
        count = 1
        for i in range(n):
            if group[i] == -1:
                a = dfs(i,count)
                dic[count] = a
                count += 1
        return group,dic

    def dfs(i,count):
        num = 0
        group[i] = count
        q = deque([])
        q.append(i)
        while q:
            bef = q.pop()

            for nex in fre[bef]:
                if group[nex] == -1:
                    group[nex] = count
                    q.append(nex)
                    num += 1
        return num
    group,dic = check()
    ans = []
    for i in range(n):
        a = group[i]
        ans.append([dic[a]-len(fre[i]),a])
    for i in range(k):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        if ans[a][1] == ans[b][1]:
            ans[a][0] -= 1
            ans[b][0] -= 1
    for i,j in ans:
        print(i,end=" ")

if __name__ == "__main__":
    main()

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

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

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


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

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.union(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block):
            ans[iam] -= 1

print(*ans, sep=' ')

Solution (Python):
from collections import deque
n, m, k =map(int, input().split())

directcount = [0] * n 
visited = [-1]  * n 
colorcount = [-1] * n 

g = []
for _ in range(n):
    g.append(deque(list()))


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


q = deque(list()) 
for i in range(n):
    q.append(i)
    color = i
    cnt = 1
    while len(q) > 0:
        nextnode = q.popleft() 
        if visited[nextnode] != -1:
            continue
        visited[nextnode] = color
        q.extend(g[nextnode]) 
        cnt += 1
    
    colorcount[color]  = cnt - 1


res = [[visited[i], colorcount[visited[i]] - (directcount[i] + 1)] for i in range(n)]


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






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