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():
    """Union Find実装"""

    def __init__(self, n):
        """要素数nで初期化する"""
        self.n = n

        
        
        self.root = [-1]*(n+1)
        
        
        
        self.rank = [0]*(n+1)

    def find(self, x):
        """ノードXのルートノードを返す"""

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

    def union(self, x, y):
        """ノードxの属するツリーとノードyの属するツリーをくっつける"""
        
        
        x = self.find(x)
        y = self.find(y)

        
        if (x == y):
            return

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

    def same(self, x, y):
        """xとyが同じ木に属するかどうか判定する"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """xが属する木のノード数を返す"""
        return -self.root[self.find(x)]
        
N, M, K = map(int, input().split())
uf = UnionFind(N)
blocks = [[] for i in range(N+1)]
friends = [0] * (N+1)

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

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

ans = [0] * N
for i in range(1, N+1):
    block_num = 0
    for b in blocks[i]:
        if uf.same(i, b):
            block_num += 1
    ans[i-1] = uf.count(i) - block_num - friends[i] - 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=[-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)])

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
i=-1
for a,b in t:
 x,y=sorted((r(a),r(b)));i+=1
 if(x!=y)*m>i:p[x]+=p[y];p[y]=x
 if(x!=y)*i<m:s[a]-=1;s[b]-=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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
 x,y=sorted((r(a),r(b)))
 if(x!=y)*m>i:p[x]+=p[y];p[y]=x
 if(x!=y)*i<m:s[a]-=1;s[b]-=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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=sorted((r(a),r(b)))
  if(x!=y)*m>i:
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if(x!=y)*i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if x==y or i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

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,s=[-1]*-~n,[-1]*-~n
for i,(a,b)in enumerate(t):
  x,y=r(a),r(b)
  if(x!=y)*m>i:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  if r(a)==r(b)or i<m:
    s[a]-=1
    s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
print(*s[1:])

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,s=[-1]*-~n,[-1]*-~n
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  s[a]-=1
  s[b]-=1
for i in range(n+1):s[i]-=p[r(i)]
for c,d in t[m:]:
  if r(c)==r(d):
    s[c]-=1
    s[d]-=1
print(*s[1:])

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,f=[-1]*-~n,[-1]*-~n
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  f[a]-=1
  f[b]-=1
a=[f[i]-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

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
f=[[]for _ in p]
for a,b in t[:m]:
  x,y=r(a),r(b)
  if x!=y:
    if x>y:x,y=y,x
    p[x]+=p[y]
    p[y]=x
  f[a]+=b,
  f[b]+=a,
a=[~len(f[i])-p[r(i)]for i in range(n+1)]
for c,d in t[m:]:
  if r(c)==r(d):
    a[c]-=1
    a[d]-=1
print(*a[1:])

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

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

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1

n, m, k = LI()
U = UnionFind(n)
AB = LIR(m)
for a, b in AB:
    U.union(a - 1, b - 1)

ans = [U.get_size(U.root(i)) - 1 for i in range(n)]
for a, b in AB:
    ans[a - 1] -= 1
    ans[b - 1] -= 1

for _ in range(k):
    c, d = LI()
    if U.is_same(c - 1, d - 1):
        ans[c - 1] -= 1
        ans[d - 1] -= 1


print(*ans)

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

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

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

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

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

n,m,k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
cd = [list(map(int, input().split())) for i in range(k)]
uf = UnionFind(n)
for a,b in ab:
    uf.union(a-1, b-1)
ans = [uf.size(i)-1 for i in range(n)]
for a,b in ab:
    ans[a-1] -= 1
    ans[b-1] -= 1
for c,d in cd:
    if uf.same(c-1, d-1):
        ans[c-1] -= 1
        ans[d-1] -= 1
print(*ans)

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

class UnionFind():
    
    
    def __init__(self,n):
        
        
        
        self.root=[-1]*n
        
        self.rnk=[0]*n
    
    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 Root_Same(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 a,b in ab:
    
    u.Unite(a-1,b-1)

ans=[u.Count(i)-1 for i in range(n)]


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

for c,d in cd:
    
    if u.Root_Same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

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

    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:
            if self.height[x] < self.height[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.height[x] == self.height[y]:
                    self.height[x] += 1

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N)
exc = [set() for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    exc[a - 1].add(b - 1)
    exc[b - 1].add(a - 1)
    uf.unite(a - 1, b - 1)
for _ in range(K):
    c, d = map(int, input().split())
    if uf.issame(c - 1, d - 1):
        exc[c - 1].add(d - 1)
        exc[d - 1].add(c - 1)

ans = [uf.group_size(i) - len(exc[i]) - 1 for i in range(N)]
print(*ans)

Solution (Python):
n,m,k=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(m)]
cd=[list(map(int,input().split()))for i in range(k)]
class UnionFind():
    def __init__(self,n):
        self.n=[-1]*n
        self.r=[0]*n
    def Find_Root(self,x):
        if self.n[x]<0:
            return x
        else:
            self.n[x]=self.Find_Root(self.n[x])
            return self.n[x]
    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.r[x]>self.r[y]:
            self.n[x]+=self.n[y]
            self.n[y]=x
        else:
            self.n[y]+=self.n[x]
            self.n[x]=y
            if self.r[x]==self.r[y]:
                self.r[y]+=1
    def Root_Same(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)
    def Count(self,x):
        return -self.n[self.Find_Root(x)]
u=UnionFind(n)
for a,b in ab:
    u.Unite(a-1,b-1)
ans=[u.Count(i)-1 for i in range(n)]
for a,b in ab:
    if u.Root_Same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1
for c,d in cd:
    if u.Root_Same(c-1,d-1):
        ans[c-1]-=1
        ans[d-1]-=1
print(*ans)

Solution (Python):
from collections import deque

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

F=[[] for _ in range(N)]
B=[[] for _ in range(N)]


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

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

q=deque([])
G=[]
visited=[0]*N
group=[-1]*N
idx=0
for i in range(N):
    if visited[i]==1:continue
    visited[i]=1
    group[i]=idx
    q.append([i,[i]])
    while q:
        n,c=q.pop()
        for j in F[n]:
            if visited[j]==0:
                c.append(j)
                visited[j]=1
                group[j]=idx
                q.append([j,c])
    G.append(c)
    idx+=1

cnt=[0]*N
for g in G:
    for i in g:
        for b in B[i]:
            if  group[i]==group[b]:
                cnt[i]+=1

ans=[0]*N

for g in G:
    for i in g:
        ans[i]=len(g)-len(F[i])-cnt[i]-1

for i in ans:
    print(str(i),end=" ")

Solution (Python):

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


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

def unite(x,y):
    x = find(x) 
    y = find(y)
    
    if x == y:
        return False
    else:
        if parents[x] > parents[y]: 
            x,y = y,x
        parents[x] += parents[y]
        parents[y] = x
        return True


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



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



parents=[-1]*n

friend = [set() for _ in range(n)]

for i in range(m): 
    a,b=map(int,input().split())
    unite(a-1,b-1)
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
    
a=[size(i)-len(friend[i])-1 for i in range(n)]

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

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

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if uf.same(c, d):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)

Solution (Python):


import sys
input = sys.stdin.readline
N, M, K=map(int, input().split())

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

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.unite(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(' '.join(map(str, [friends_chain.count(i) - len(friend_or_block[i]) - 1 for i in range(N)])))

Solution (Python):


class DSU:
    def __init__(self, n):
        self.__parent = [i for i in range(n+1)]
        self.__size = [1 for _ in range(n+1)]
        self.n = n

    def parentOf(self,x):
        if self.__parent[x] != x:
            self.__parent[x] = self.parentOf(self.__parent[x])
        return self.__parent[x]
    
    def sizeOf(self,x):
        return self.__size[self.parentOf(x)]
    
    def makeUnion(self,x,y):
        p = self.parentOf(x)
        q = self.parentOf(y)
        if p==q:
            return
        if self.__size[p] < self.__size[q]:
            p,q = q,p
        self.__parent[q] = p
        
        self.__size[p] += self.__size[q]
        
    


if __name__ == "__main__":
    n,m,k = (int(x) for x in input().split())
    friendEdge = [ [int(x) for x in input().split()] for _ in range(m) ]
    enemyEdge = [ [int(x) for x in input().split()] for _ in range(k) ]

    d  = DSU(n+1)

    for (u,v) in friendEdge:
        d.makeUnion(u,v)
    

    outEdge = dict()
    for (u,v) in enemyEdge+friendEdge:
        if u not in outEdge:
            outEdge[u] = list()
        if v not in outEdge:
            outEdge[v] = list()
        outEdge.get(u).append(v)
        outEdge.get(v).append(u)

    ans = [0] * n
    for i in range(1,n+1):
        ans[i-1] = d.sizeOf(i) - 1
        
        for v in outEdge.get(i,list()):
            if d.parentOf(i) == d.parentOf(v):
                
                ans[i-1] -= 1

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

Solution (Python):
import sys


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)
direct = [set() for _ in range(N)]
IN = sys.stdin.readlines()
for i in range(M):
    a, b = map(int, IN[i].split())
    a -= 1; b -= 1
    uf.union(a, b)
    direct[a].add(b)
    direct[b].add(a)
for i in range(M, M + K):
    a, b = map(int, IN[i].split())
    a -= 1; b -= 1
    if uf.find(a) == uf.find(b):
        direct[a].add(b)
        direct[b].add(a)
ans = []
for i in range(N):
    cnt = -uf.parents[uf.find(i)] - 1
    cnt -= len(direct[i])
    ans.append(cnt)

print(*ans)

Solution (Python):

"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
part_time1 = 0
part_time2 = 0




    
time_all.append(time.time()-start)

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = [False]*N
label = [0]*N
todo = deque()
num = 0
minus = [0]*N

time_all.append(time.time()-start)
 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1

time_all.append(time.time()-start)
count = 0
for k in range(N):
    time1 = time.time()
    num+=1
    if seen[k] == False:
        H = k
    else:
        continue
    todo += [(H)]
    seen[H] = True
    group = []
    part_time1 += time.time() - time1
    while not len(todo) == 0:
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            count+=1
            if seen[i] == False:
                todo += [i]
                seen[i] = True

time_all.append(time.time()-start)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1
    
time_all.append(time.time()-start)

for i in range(N):
    print(accompany[label[i]] + minus[i]-1)

time_all.append(time.time()-start)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
class UnionFind():
    def __init__(self, n):
        self.parents = [-1]*n
        self.count = [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
        self.parents[y] = x
        self.count[x] +=  self.count[y]
n,m,k = map(int,input().split())
uf = UnionFind(n)
block = [[] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1) 
    block[a-1].append(b-1)
    block[b-1].append(a-1)
for i in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1].append(d-1)
        block[d-1].append(c-1)
ans = []
for i in range(n):
    ans.append(uf.count[uf.find(i)]-len(block[i])-1)
print(" ".join(map(str,ans)))

Solution (Python):

"""
Created on Mon Mar  2 06:12:32 2020

@author: naoki
"""
from collections import deque
import time
start = time.time()
time_all = []
part_time1 = 0
part_time2 = 0




    
time_all.append(time.time()-start)

N ,M ,K = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
C = [list(map(int,input().split())) for _ in range(K)]
connection = [[] for i in range(N)]
seen = [False]*N
label = [0]*N
todo = deque()
num = 0
minus = [0]*N

time_all.append(time.time()-start)
 
for pair in A:
    connection[pair[0]-1] += [(pair[1]-1)]
    connection[pair[1]-1] += [(pair[0]-1)]
    minus[pair[0]-1] -= 1
    minus[pair[1]-1] -= 1

time_all.append(time.time()-start)
count = 0
for k in range(N):
    time1 = time.time()
    num+=1
    if seen[k] == False:
        H = k
    else:
        continue
    todo += [(H)]
    seen[H] = True
    group = []
    part_time1 += time.time() - time1
    while not len(todo) == 0:
        current = todo.pop()
        label[current] = num
        group += [current]
        for i in connection[current]:
            count+=1
            if seen[i] == False:
                todo += [i]
                seen[i] = True

time_all.append(time.time()-start)

for pair in C:
    if label[pair[0]-1] == label[pair[1]-1]:
        minus[pair[0]-1] -= 1
        minus[pair[1]-1] -= 1
accompany = {i:0 for i in range(1,num+1)}
for i in range(N):
    accompany[label[i]] += 1
    
time_all.append(time.time()-start)

print(" ".join(map(lambda x,y : str(accompany[x]+y-1), label, minus)))

time_all.append(time.time()-start)

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)
direct = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    uf.union(a, b)
    direct[a].add(b)
    direct[b].add(a)
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if uf.find(a) == uf.find(b):
        direct[a].add(b)
        direct[b].add(a)
ans = []
for i in range(N):
    cnt = -uf.parents[uf.find(i)] - 1
    cnt -= len(direct[i])
    ans.append(cnt)

print(*ans)

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):
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):
import sys
input = sys.stdin.readline
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    parent = [-1] * N

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

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

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

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

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        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 same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M, K=map(int, input().split())
    friend_or_block = [0] * N
    parent = [-1] * N

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

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

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

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

    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        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 same(c, d):
            friend_or_block[c] += 1
            friend_or_block[d] += 1

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

if __name__ == '__main__':
    main()