Problem: 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?

Submission attempts (in order):
N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
zumi = []
before = 0
for i in range(N):
  if i not in zumi:
    zumi.append(i)
    que = fri[i]
    after = before + len(fri[i])
    while que:
      tmp = que.pop()
      zumi.append(tmp)
      for x in fri[tmp]:
        if (x not in zumi) and (x not in que):
          que.append(x)
          after += 1
    for i in range(before, after+1):
      ans[zumi[i]] = after - before - len(fri[i])
    before = after + 1
  else:
    continue
print(*ans)


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(roots())

def main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  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):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == "__main__":
  main()
    
  
  
  
      
      
      

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 main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  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):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == '__main__':
  main()

N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
zumi = []
before = 0
for i in range(N):
  if i not in zumi:
    zumi.append(i)
    que = fri[i]
    after = before + len(fri[i])
    while que:
      tmp = que.pop()
      zumi.append(tmp)
      for x in fri[tmp]:
        if (x not in zumi) and (x not in que):
          que.append(x)
          after += 1
    for i in range(before, after+1):
      ans[zumi[i]] = after - before - len(fri[i])
    for j in range(before, after):
      for k in range(j+1, after + 1):
        if zumi[k] in blo[zumi[j]]:
          ans[zumi[k]] -= 1
          ans[zumi[j]] -= 1
    before = after + 1
  else:
    continue
print(*ans)

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 main(): 
  n, m, k = map(int, input().split())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  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):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

main()

N, M, K = map(int, input().split())
ans = [0] * N
fri = [[] for i in range(N)]
blo = [[] for i in range(N)]
kouho =[[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
for i in range(K):
  c,d = map(int, input().split())
  blo[c-1].append(d-1)
  blo[d-1].append(c-1)
for i in range(N):
  zumi = [i]
  stack = fri[i]
  while stack:
    tmp = stack.pop()
    zumi.append(tmp)
    for k in fri[tmp]:
      if k not in zumi and k not in stack:
        stack.append(k)
        if k not in blo[i] and k not in fri[i]:
          kouho[i] += 1
print(*kouho)
  

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

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())
  uf = UnionFind(n)
  ans = [0] * n
  deg = [0] * n
  for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    deg[a] += 1
    deg[b] += 1
  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):
    ans[i] = uf.size(i) - deg[i] - 1
  print(' '.join(map(str,ans)))

if __name__ == "__main__":
  main()

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Accepted