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: Wrong Answer

Solution code:
class UnionFind:
  def __init__(self, n):
    self.n = n
    self.g = [i for i in range(n)]
    self.nmembers = [1 for i in range(n)]
  def __len__(self):
    return self.n
  def __str__(self):
    return "group:{}\nnmembers:{}".format(self.g,self.nmembers)
  def __getitem__(self,x):
    return self.g[x]
  def merge(self, x, y):
    gx = self.whichgroup(x)
    gy = self.whichgroup(y)
    if gx != gy:
      nx = self.nmembers[gx]
      ny = self.nmembers[gy]
      ming = min(gx, gy)
      maxg = gx + gy - ming
      self.g[maxg] = ming
      self.nmembers[maxg] = 0
      self.nmembers[ming] = nx + ny
    
  def whichgroup(self, x):
    if x != self.g[x]:
      self.g[x] = self.whichgroup(self.g[x])
      self.nmembers[x] = 0
      return self.g[x]
    else:
      return x

N, M, K = map(int, input().split())
UF = UnionFind(N)
F = [0 for i in range(N)]
B = [0 for i in range(N)]
#print(UF)
for i in range(M):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  #print("x:{}, y:{}".format(x, y))
  UF.merge(x, y)
  F[x] += 1
  F[y] += 1
for i in range(K):
  x, y = map(int, input().split())
  x, y = x-1, y-1
  
  gx = UF.whichgroup(x)
  gy = UF.whichgroup(y)
  if gx == gy:
    B[x] += 1
    B[y] += 1

ans = []
for i in range(N):
  ans.append(UF.nmembers[UF[i]]-B[i]-F[i]-1)
print(*ans)

Submission status: Wrong Answer

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

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


def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

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

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

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

ans=[]

for i in range(n):
    cnt=size[find(i)]
    xxx=list(set(graph[i]))
    cnt-=len(xxx)
    cnt-=1
    ans+=[str(cnt)]


print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

friend = [[] for _ in range(n+1)]
block = [[] for _ in range(n+1)]

for i in range(m):
  a,b = map(int,input().split())
  friend[a].append(b)
  friend[b].append(a)
  
for i in range(k):
  c,d = map(int,input().split())
  block[c].append(d)
  block[d].append(c)

for j in range(1,n+1):
  dist = [-1] * (n+1)
  dist[0] = 0
  dist[j] = 0

  d = deque()
  d.append(j)

  while d:
    v = d.popleft()
    for i in friend[v]:
      if dist[i] != -1:
        continue
      dist[i] = dist[v] + 1
      d.append(i)

  F = dist[1:]

  dist2 = [-1] * (n+1)
  dist2[0] = 0
  dist2[j] = 0

  d2 = deque()
  d2.append(j)

  while d2:
    v = d2.popleft()
    for i in block[v]:
      if dist2[i] != -1:
        continue
      dist2[i] = dist2[v] + 1
      d2.append(i)

  B = dist2[1:]
  
  cnt = 0
  for i in range(n):
    if F[i] > 1 and B[i] < 1:
      cnt += 1
  print(cnt, end=' ')

Submission status: Wrong Answer

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

f_adj_list = [[] for i in range(n)]
b_adj_list = [[] for i in range(n)]

for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  f_adj_list[_].append(__)
  f_adj_list[__].append(_)
  
for j in range(k):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  b_adj_list[_].append(__)
  b_adj_list[__].append(_)
  
  
group_id = [None for i in range(n)]
for i in range(n):
  # i から DFS
  newly_visited = [i]
  group_id[i] = i
  while len(newly_visited) > 0:
    now = newly_visited.pop()
    for j in f_adj_list[now]:
      if group_id[j] is not None: continue
      newly_visited.append(j)
      group_id[j] = i

# group_id
# print(group_id)

# 連結成分のサイズ
from collections import Counter
cnt = Counter(group_id)
# cnt[5] = 7

for i in range(n):
  ans = cnt[group_id[i]]
  ans -= 1 # 自分自身
  ans -= len(f_adj_list[i]) # 直接の友達
  for j in b_adj_list[i]:
    if group_id[i] == group_id[j]:
      ans -= 1
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import copy as cp
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1))) ##union-findの親リスト
rank=[1]*(N+1) #unionの大きさ

path=dd(list)  ##直接つながっている枝
for _ in range(M):
    A,B=map(int, input().split())
    path[A].append(B)
    path[B].append(A)
    union(A,B)
 
fd=dd(list)   ##ブロック関係
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

fl=dd(list)  ##フレンド候補
             ##union-findで作成した集合をリスト化
ans=[]

for i in range(1,N+1):
    for j in range(i+1,N+1):
        if par[i]==par[j]:
            ##直接つながっておらずブロック関係でもないものを
            ##フレンド候補とする
            if j not in fd[i] and j not in path[i]:
                fl[i].append(j)
            if i not in fd[j] and i not in path[j]:
                fl[j].append(i)  
    ans.append(len(fl[i]))

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

Submission status: Wrong Answer

Solution code:
import sys
import copy as cp
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1)))
rank=[1]*(N+1)

path=dd(list)  ##直接つながっている枝

for _ in range(M):
    A,B=map(int, input().split())
    path[A].append(B)
    path[B].append(A)
 
#print('path')
#print(path)

fd=dd(list)   ##ブロック関係
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

#print('fd')
#print(fd)
      
for i in path:
    for j in path[i]:
        union(i,j)

fl=dd(list)  ##フレンド候補
ans=[]
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if par[i]==par[j]:
            if j not in fd[i] and j not in path[i]:
                fl[i].append(j)
            if i not in fd[j] and i not in path[j]:
                fl[j].append(i)  
    ans.append(len(fl[i]))

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

Submission status: Wrong Answer

Solution code:
import sys
import copy as cp
from collections import defaultdict as dd
sys.setrecursionlimit(10**8)

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
    else:
        par[b]=a
        rank[a]+=rank[b]       

    return
 

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

par=(list(range(N+1)))
rank=[1]*(N+1)

path=dd(list)  ##直接つながっている枝

for _ in range(M):
    A,B=map(int, input().split())
    path[A].append(B)
    path[B].append(A)
 
#print('path')
#print(path)

fd=dd(list)   ##ブロック関係
for _ in range(K):
    C,D=map(int, input().split())
    fd[C].append(D)  ##ブロック関係をメモ
    fd[D].append(C)

#print('fd')
#print(fd)
      
for i in path:
    for j in path[i]:
        union(i,j)

fl=dd(list)  ##フレンド候補
for i in range(1,N):
    for j in range(i+1,N+1):
        if par[i]==par[j]:
            fl[i].append(j)
            fl[j].append(i)  
#print('fl')
#print(fl)
            
ans=[]
for i in range(1,N+1):
    for j in path[i]:
        if j in fl[i]:
            fl[i].remove(j)
    for j in fd[i]:
        if j in fl[i]:
            fl[i].remove(j)
    ans.append(len(fl[i]))
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

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[root[i]]-len(l[i])-1,end=" ")

Submission status: Wrong Answer

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=[0 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]+=1;l[b]+=1
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a]+=1;l[b]+=1
   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[root[i]]-l[i]-1,end=" ")

Submission status: Wrong Answer

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

friend=[[] for i in range(n)]
block=[[] for i in range(n)]
lst=[]

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

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


par=[i for i in range(n)]
size=[1 for i in range(n)]
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

for i in lst:
    union(i[0],i[1])

ans=[]

for i in range(n):
    ans.append(str(size[find(i)]-len(set(friend[i]+block[i]))-1))

print(' '.join(ans))

Submission status: Wrong Answer

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 = []

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

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

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: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        flag[i] = group
        member_tmp = [i]
        while len(deque) > 0:
            target = deque.popleft()
            flag[target] = group
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []
    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        candidate = len(groups[i_group]) - len(friends[i])
        for blocking in blocks[i]:
            if blocking in groups[i_group]:
                candidate -= 1
        ans.append(candidate)
    print(" ".join(map(str, ans)))


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        flag[i] = group
        member_tmp = [i]
        while len(deque) > 0:
            target = deque.popleft()
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []
    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        candidate = len(groups[i_group]) - len(friends[i]) - 1
        for blocking in blocks[i]:
            if blocking in groups[i_group]:
                candidate -= 1
        ans.append(candidate)
    print(" ".join(map(str, ans)))


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        member_tmp = [i]
        while len(deque) > 0:
            target = deque.popleft()
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []
    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        candidate = len(groups[i_group]) - len(friends[i]) - 1
        for blocking in blocks[i]:
            if blocking in groups[i_group]:
                candidate -= 1
        ans.append(candidate)
    print(" ".join(map(str, ans)))


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        member_tmp = [i]
        while len(deque) > 0:
            target = deque.popleft()
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []
    len_groups = [0] * len(groups)
    for i in range(len(groups)):
        groups[i] = set(groups[i])
        len_groups[i] = len(groups[i])

    for i in range(N):
        i_group = flag[i]
        no_effeck_blocks = len(set(blocks[i]) - groups[i_group]
                               )
        friend_candidates = len(groups[i_group]) - \
            (len(blocks[i]) - no_effeck_blocks)
        num_group = friend_candidates - len(friends[i]) - 1
        ans.append(num_group)

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


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        member_tmp = []
        while len(deque) > 0:
            target = deque.popleft()
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []

    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        no_effeck_blocks = len(set(blocks[i]) - groups[i_group]
                               )
        friend_candidates = len(groups[i_group]) - \
            (len(blocks[i]) - no_effeck_blocks)
        num_group = friend_candidates - len(friends[i]) - 1
        ans.append(num_group)

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


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N, M, K = MI()
    friends = [[] for i in range(N)]
    blocks = [[] for i in range(N)]

    for _ in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        friends[a].append(b)
        friends[b].append(a)

    for _ in range(K):
        a, b = MI()
        a -= 1
        b -= 1
        blocks[a].append(b)
        blocks[b].append(a)

    groups = []
    flag = [-1] * N
    group = 0
    for i in range(N):
        if flag[i] != -1:
            continue
        deque = cl.deque(friends[i])
        member_tmp = []
        while len(deque) > 0:
            target = deque.popleft()
            friends_i = friends[target]
            for frend in friends_i:
                if flag[frend] != -1:
                    continue
                member_tmp.append(frend)
                flag[frend] = group
                deque.append(frend)
        groups.append(member_tmp)
        group += 1

    ans = []

    for i in range(len(groups)):
        groups[i] = set(groups[i])

    for i in range(N):
        i_group = flag[i]
        num_group = len(groups[i_group] - set(friends[i]) - set(blocks[i])) - 1
        ans.append(num_group)

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


main()

Submission status: Wrong Answer

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(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.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m, k = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    fb = [0]*n
    i = 0
    for x in sys.stdin.buffer.readlines():
        if i < m:
            a, b = map(int, x.split())
            fb[a-1] += 1
            fb[b-1] += 1
            uf.union(a-1, b-1)
        else:
            c, d = map(int, x.split())
            fb[c-1] += 1
            fb[d-1] += 1
        i += 1

    ans = [-uf.table[uf._root(i)]-1-fb[i] for i in range(n)]
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

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

    friends = [set() for _ in [0] * (N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in [0] * (N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        friends_chain.append(set())
        while q:
            now = q.pop()
            if seen[now] != -1:
                continue
            seen[now] = cnt
            for next in friends[now]:
                friends_chain[-1].add(now)
                q.append(next)
        cnt += 1

    ans = []
    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        tmp_ans = len(res) - len(friends[person]) - 1
        for block in blocks[person]:
            tmp_ans -= 1 if block in res else 0
        ans.append(tmp_ans)
    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

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

    friends = [set() for _ in [0] * (N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        friends[a].add(b)
        friends[b].add(a)
    blocks = [set() for _ in [0] * (N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        blocks[c].add(d)
        blocks[d].add(c)

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for person in range(1, N + 1):
        if seen[person] != -1:
            continue
        q = deque([person])
        chain = set()
        while q:
            now = q.pop()
            if seen[now] != -1:
                continue
            seen[now] = cnt
            for next in friends[now]:
                chain.add(now)
                q.append(next)
        friends_chain.append(chain)
        cnt += 1

    for person in range(1, N + 1):
        res = friends_chain[seen[person]]
        ans = len(res) - 1
        for block in blocks[person]:
            # res.discard(block)
            ans -= 1 if block in res else 0
        for friend in friends[person]:
            # res.discard(friend)
            ans -= 1 if friend in res else 0
        print(ans, end=' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]
    CD = [tuple(map(int, input().split())) for _ in [0] * K]

    friends = [set() for _ in [0] * (N + 1)]
    for f in AB:
        friends[f[0]].add(f[1])
        friends[f[1]].add(f[0])
    blocks = [set() for _ in [0] * (N + 1)]
    for b in CD:
        blocks[b[0]].add(b[1])
        blocks[b[1]].add(b[0])

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for i in range(1, N + 1):
        if seen[i] != -1:
            continue
        q = deque([i])
        chain = set()
        while q:
            now = q.pop()
            if seen[now] != -1:
                continue
            seen[now] = cnt
            for next in friends[now]:
                chain.add(now)
                q.append(next)
        friends_chain.append(chain)
        cnt += 1

    ans = [0] * (N + 1)
    for person in range(1, N + 1):
        res = set(friends_chain[seen[person]])
        for block in blocks[person]:
            res.discard(block)
        for friend in friends[person]:
            res.discard(friend)
        ans[person] = len(res) - 1
    
    for hoge in ans[1:]:
        print(hoge, end=' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque

    N, M, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]
    CD = [tuple(map(int, input().split())) for _ in [0] * K]

    friends = [set() for _ in [0] * (N + 1)]
    for f in AB:
        friends[f[0]].add(f[1])
        friends[f[1]].add(f[0])
    blocks = [set() for _ in [0] * (N + 1)]
    for b in CD:
        blocks[b[0]].add(b[1])
        blocks[b[1]].add(b[0])

    friends_chain = []
    seen = [-1] * (N + 1)
    cnt = 0
    for i in range(1, N + 1):
        q = deque([i])
        chain = set()
        while q:
            now = q.pop()
            if seen[now] != -1:
                continue
            seen[now] = cnt
            for next in friends[now]:
                chain.add(now)
                q.append(next)
        friends_chain.append(chain)
        cnt += 1

    ans = [0] * (N + 1)
    for person in range(1, N + 1):
        res = set(friends_chain[seen[person]])
        for block in blocks[person]:
            res.discard(block)
        for friend in friends[person]:
            res.discard(friend)
        ans[person] = len(res) - 1
    
    for hoge in ans[1:]:
        print(hoge, end=' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def makenetwork():
  for n in range(1,N+1):
    visited=set((n,))
    while visited:
      v=visited.pop()
      D[n].append(v)
      for i in F[v]:
        if i not in D[n]:
          visited.add(i)


def main():
  makenetwork()
  #print(D)
  #ans=[0]*(N+1)
  #for n in range(1, N+1):
  #	ans[n]=len(D[n]) - len(F[n]) - len(set(D[n])&set(B[n])) - 1
  #print(*ans[1:])


if __name__=='__main__':
  N, M, K = map(int, input().split())
  F=[[] for n in range(N+1)]
  for m in range(M):
    a, b = map(int, input().split())
    F[a]+=[b]
    F[b]+=[a]
  B=[[] for n in range(N+1)]
  for k in range(K):
    c, d = map(int, input().split())
    B[c]+=[d]
    B[d]+=[c]
  D=[[] for n in range(N+1)]
  #print(F)
  #print(B)
  main()