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



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Accepted

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        
    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]
    
n, m, k = map(int, input().split())
friends = UnionFind(n)
f_or_b = [1] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    friends.unite(a, b)
    f_or_b[a] += 1
    f_or_b[b] += 1
for i in range(k):
    c, d = map(int, input().split())
    if friends.is_same(c, d):
        f_or_b[c] += 1
        f_or_b[d] += 1
print(*[friends.size(i) - f_or_b[i] for i in range(1, n + 1)])

Submission status: Accepted

Solution code:
from collections import deque
f=lambda:map(int,input().split())
r=range
n,m,k=f()
F=[deque([])for _ in r(n)]
A=[0]*n
B=[-1]*n
C=[-1]*n
Q=deque([])
for _ in r(m):a,b=f();a-=1;b-=1;F[a].append(b);F[b].append(a);A[a]+=1;A[b]+=1
for i in r(n):
  Q.append(x:=i)
  y=0
  while Q:
    z=Q.popleft()
    if B[z]>-1:continue
    B[z]=x
    Q.extend(F[z])
    y+=1
  C[x]=y
D=[[B[i],C[B[i]]-A[i]-1]for i in r(n)]
for _ in r(k):
  c,d=f()
  c,d=c-1,d-1
  if D[c][0]==D[d][0]:D[c][1]-=1;D[d][1]-=1
print(*[d[1] for d in D])

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.d[self.find(x)]

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

deg = [0]*100005
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    deg[a] += 1
    deg[b] += 1
    uf.unite(a, b)
for _ in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if uf.same(c, d):
        deg[c] += 1
        deg[d] += 1
for i in range(n):
    print(uf.size(i) - 1 - deg[i], end="")
    if i == n-1:
        print()
    else:
        print(" ", end="")

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M, K = map(int, input().split())
Network = UnionFind(N)
Friend = [0] * N  #人indexの友達の数
BlockInNetwork = [0] * N  #同じグループの中でブロックされている人の数

for _ in range(M):  #友達関係
    a, b = map(int, input().split())
    Network.union(a-1, b-1)
    Friend[a-1] += 1
    Friend[b-1] +=1

for _ in range(K): #ブロック関係
    c, d = map(int, input().split())
    if Network.same(c-1, d-1):  #same=aとbが同じグループか True or False
        BlockInNetwork[c-1] += 1
        BlockInNetwork[d-1] += 1

out = [0] * N  #友達候補の数 = そのグループの数 - 直の友達の数 - ブロックされている人の数 - 自分
for i in range(N):
    out[i] = Network.size(i) - Friend[i] - BlockInNetwork[i] - 1
print(*out)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

N,M,K = map(int,input().split())
tree = UnionFind(N)
friends = [list(map(int,input().split())) for _ in range(M)]
blocks = [list(map(int,input().split())) for _ in range(K)]
for a,b in friends:
    tree.unite(a,b)
for a,b in friends:
    tree.unite(a,b)

ans = [tree.size[tree.parents[i]]-1 for i in range(N+1)]
for a,b in friends:
    ans[a] -= 1
    ans[b] -= 1

for a,b in blocks:
    if tree.parents[a] == tree.parents[b]:
        ans[a] -= 1
        ans[b] -= 1

ans = [str(ans[i]) for i in range(1,N+1)]
print(" ".join(ans))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return
        else:
            if x > y:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return

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

u = UnionFind(n)
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
    u.unite(a, b)
for c, d in cd:
    c, d = c-1, d-1
    l[c].add(d)
    l[d].add(c)
ans = [0] * n
for i in range(n):
    r = u.root(i)
    bl = 0
    for j in l[i]:
        if u.root(j) == r:
            bl += 1
    ans[i] = -u.parents[r] - len(f[i]) - bl - 1
print(' '.join(list(map(str, ans))))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M,K=map(int,input().split())
tree=UnionFind(N)
not_friend_candidates=[]

for i in range(M):
  A,B=list(map(int,input().split()))
  A-=1
  B-=1
  tree.union(A,B)
  not_friend_candidates.append([A,B])

for j in range(K):
  C,D=list(map(int,input().split()))
  C-=1
  D-=1
  not_friend_candidates.append([C,D])


ans=[0]*N
for i,j in not_friend_candidates:
  if tree.same(i,j):
    ans[i]-=1
    ans[j]-=1
for i in range(N):
  ans[i]+=tree.size(i)-1
print(*ans)

Submission status: Accepted

Solution code:
N,M,K=list(map(int,input().split()))
root=[i for i in range(N)]
height=[1 for i in range(N)]
l=[set() for i in range(N)]
mem=[0]*N
def find(n):
   f=n
   while n != root[n]:
      n=root[n]
   root[f]=n
   return n
def union(a,b):
   A=find(a)
   B=find(b)
   if A==B:
      return
   elif height[A]<height[B]:
      height[B]+=height[A]
      height[A]=0
      root[A]=B
   else:
      root[B]=A
      height[A]+=height[B]
      height[B]=0
def same(a,b):
   A=find(a)
   B=find(b)
   if A==B:
      l[a].add(b)
      l[b].add(a)
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].add(b)
   l[b].add(a)
   union(a,b)
for j in range(K):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   same(a,b)
for i in range(N):
   print(height[find(i)]-len(l[i])-1,end=" ")

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
Network = UnionFind(N)
Friend = [0] * N
BlockInNetwork = [0] * N

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

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

out = [0]*N
for i in range(N):
    out[i]=Network.size(i)-Friend[i]-BlockInNetwork[i] - 1
print(*out)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[] for _ in range(n)]
a=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    friend[x-1].append(y-1)
    friend[y-1].append(x-1)
    a.union(x-1,y-1)
for i in range(k):
    x,y=map(int,input().split())
    block[x-1].append(y-1)
    block[y-1].append(x-1)
ans=[]
for i in range(n):
    ans.append(a.size(i)-len(friend[i])-sum(a.same(i,j) for j in block[i])-1)
print(*ans)

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,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())

def do():
    n,m,k=INTM()
    uf=UnionFind(n)
    fri=[[] for i in range(n)]
    blo=[[] for i in range(n)]
    for i in range(m):
        a,b=INTM()
        a-=1
        b-=1
        fri[a].append(b)
        fri[b].append(a)
        uf.union(a,b)
    for i in range(k):
        c,d=INTM()
        c-=1
        d-=1
        blo[c].append(d)
        blo[d].append(c)

    ans=[]

    for i in range(n):
        blos=0
        for j in blo[i]:
            if uf.same(i,j):
                blos+=1
        
        ans.append(uf.size(i)-1-len(fri[i])-blos)
    
    print(*ans)




if __name__=='__main__':
    do()

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
c = [0] * (N + 1)
C = [0] * K
D = [0] * K
uf = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    c[a] += 1
    c[b] += 1
for i in range(K):
    C[i], D[i] = map(int, input().split())


for i in range(1,N + 1):
    c[i] = uf.size(i-1) - c[i] - 1
for i in range(K):
    if uf.same(C[i]-1, D[i]-1):
        c[C[i]] -= 1
        c[D[i]] -= 1

for i in range(1, N+1):
    print(c[i], end=" ")

Submission status: Accepted

Solution code:
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())
uf=UnionFind(n)
friend=[[] for _ in range(n)]
brock=[[] for _ in range(n)]
ans=[]
for _ in range(m):
    a,b=map(int,input().split())
    friend[a-1].append(b-1)
    friend[b-1].append(a-1)
    uf.union(a-1,b-1)
for _ in range(k):
    c,d=map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)
for i in range(n):
    ans.append(uf.size(i)-len(friend[i])-sum([uf.same(i,j) for j in brock[i]])-1)
print(*ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n,m,k=map(int,input().split())
uf=UnionFind(n)
edge=[[] for _ in range(n)]
brock=[[] for _ in range(n)]
ans=[]
for _ in range(m):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    uf.union(a-1,b-1)
for _ in range(k):
    c,d=map(int,input().split())
    brock[c-1].append(d-1)
    brock[d-1].append(c-1)
for i in range(n):
    ans.append(uf.size(i)-len(edge[i])-sum([uf.same(i,j) for j in brock[i]])-1)
print(*ans)

Submission status: Accepted

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

def main():
    N, M, K = map(int, input().split())
    friend = UnionFind(N)
    direct_friend = [0] * N
    block = [0] * N

    for _ in range(M):
        a, b = map(int, input().split())
        friend.union(a-1, b-1)
        direct_friend[a-1] += 1
        direct_friend[b-1] += 1
    
    for _ in range(K):
        c, d = map(int, input().split())
        if friend.same(c-1, d-1):
            block[c-1] += 1
            block[d-1] += 1

    for i in range(N):
        print(friend.size(i) - direct_friend[i] - block[i] - 1, end=" ")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*(n+1)
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

all1 = [0]*(n)

uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.unite(a,b)
    a,b = a-1,b-1
    
    all1[a] +=1
    all1[b] +=1
#print(all1)
ans = [uf.size(x)-1-all1[x-1] for x in range(1,n+1)]
#print(ans)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a].append(b)
    friend[b].append(a)
for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    block[c].append(d)
    block[d].append(c)
seen=[-1]*n
def dfs(graph,v,top):
    seen[v]=top
    top_count[top]+=1
    for nv in graph[v]:
        if seen[nv]!=-1:
            continue
        dfs(graph,nv,top)
top=0
top_count=[0]
for v in range(n):
    count=0
    if seen[v]!=-1:
        continue
    dfs(friend,v,top)
    top_count.append(0)
    top+=1


for i in range(n):
    ans=top_count[seen[i]]-len(friend[i])-1
    cnt=0
    for v in block[i]:
        if seen[v]==seen[i]:
            cnt+=1
    ans-=cnt
    print(ans,end=' ')

Submission status: Accepted

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


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

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

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

        if x == y:
            return
        if self.size[x] > self.size[y]:
            x, y = y, x
        self.par[x] = y
        self.size[y] += self.size[x]


uf = UnionFind(N)
fri = []
rst = [0]*N

for m in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    fri.append((A, B))
    uf.unite(A, B)

for i in range(N):
    ind = uf.find(i)
    rst[i] = uf.size[ind]-1

for f in fri:
    A, B = f
    if uf.par[A] == uf.par[B]:
        rst[A] -= 1
        rst[B] -= 1

for k in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if uf.par[C] == uf.par[D]:
        rst[C] -= 1
        rst[D] -= 1

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

Submission status: Accepted

Solution code:
"""/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Union-Find！Union-Find！Union-Find！Union-Findぅぅうううわぁああああああああああああああああああああああん！！！
あぁああああ…ああ…あっあっー！あぁああああああ！！！Union-FindUnion-FindUnion-Findぅううぁわぁああああ！！！
あぁクンカクンカ！クンカクンカ！スーハースーハー！スーハースーハー！いい匂いだなぁ…くんくん
んはぁっ！Union-Findたんの桃色ブロンドの髪をクンカクンカしたいお！クンカクンカ！あぁあ！！
間違えた！モフモフしたいお！モフモフ！モフモフ！髪髪モフモフ！カリカリモフモフ…きゅんきゅんきゅい！！
小説12巻のUnion-Findたんかわいかったよぅ！！あぁぁああ…あああ…あっあぁああああ！！ふぁぁあああんんっ！！
アニメ2期放送されて良かったねUnion-Findたん！あぁあああああ！かわいい！Union-Findたん！かわいい！あっああぁああ！
コミック2巻も発売されて嬉し…いやぁああああああ！！！にゃああああああああん！！ぎゃああああああああ！！
ぐあああああああああああ！！！コミックなんて現実じゃない！！！！あ…小説もアニメもよく考えたら…
U n i o n - F i n d ち ゃ ん は 現 実 じ ゃ な い？にゃあああああああああああああん！！うぁああああああああああ！！
そんなぁああああああ！！いやぁぁぁあああああああああ！！はぁああああああん！！う　し　た　ぷ　に　き　あ　王　国　笑ぁああああ！！
この！ちきしょー！やめてやる！！現実なんかやめ…て…え！？見…てる？表紙絵のUnion-Findちゃんが僕を見てる？
表紙絵のUnion-Findちゃんが僕を見てるぞ！Union-Findちゃんが僕を見てるぞ！挿絵のUnion-Findちゃんが僕を見てるぞ！！
アニメのUnion-Findちゃんが僕に話しかけてるぞ！！！よかった…世の中まだまだ捨てたモンじゃないんだねっ！
いやっほぉおおおおおおお！！！僕にはUnion-Findちゃんがいる！！やったよdefault dict！！ひとりでできるもん！！！
あ、コミックのUnion-Findちゃああああああああああああああん！！いやぁあああああああああああああああ！！！！
あっあんああっああんあset様ぁあ！！さ、最小全域木ー！！Dijkstraぁああああああ！！！セグ木ぃいいい！！
ううっうぅうう！！俺の想いよUnion-Findへ届け！！う　し　た　ぷ　に　き　あ　王　国　笑のUnion-Findへ届け！
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////"""
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if self.parents[x] == x:
            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.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k=map(int,input().split())
uf=UnionFind(n)
friends=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    friends[a-1]+=1
    friends[b-1]+=1
block=[[] for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d)
    block[d-1].append(c)
ans=[0]*n
cnt=[0]*n
for i in range(n):
    cnt[i]=uf.find(i)
for i in range(n):
    num1=uf.size[uf.find(i)]-friends[i]-1
    num2=cnt[i]
    for j in range(len(block[i])):
        if num2==cnt[block[i][j]-1]:
            num1-=1
    ans[i]=num1
print(*ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if self.parents[x] == x:
            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.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m,k=map(int,input().split())
uf=UnionFind(n)
friends=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1,b-1)
    friends[a-1]+=1
    friends[b-1]+=1
block=[[] for _ in range(n)]
for i in range(k):
    c,d=map(int,input().split())
    block[c-1].append(d)
    block[d-1].append(c)
ans=[0]*n
cnt=[0]*n
for i in range(n):
    cnt[i]=uf.find(i)
for i in range(n):
    num1=uf.size[uf.find(i)]-friends[i]-1
    num2=cnt[i]
    for j in range(len(block[i])):
        if num2==cnt[block[i][j]-1]:
            num1-=1
    ans[i]=num1
print(*ans)