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: Time Limit Exceeded

Solution code:
class UnionFind(object):
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a] += 1
    else:
        fr[a] = 1

    if fr.get(b) is not None:
        fr[b] += 1
    else:
        fr[b] = 1

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if bl.get(c) is not None:
        bl[c].append(d)
    else:
        bl[c] = [d]

    if bl.get(d) is not None:
        bl[d].append(c)
    else:
        bl[d] = [c]


for i in range(N):
    s = uf.get_size(i) - 1

    for b in bl.get(i, []):
        if uf.is_same(i, b):
            s -= 1

    s -= fr.get(i, 0)
    print(s)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
A = set([tuple(map(int, input().split())) for _ in range(M)])
C = set([tuple(map(int, input().split())) for _ in range(K)])
tmpX = set()

def mySearch(i):
  global tmpX
  # 友達を探す
  tmp = set()
  for a in A:
    if a[0] == i:
      # 既に調べた人を除外する
      if a[1] not in tmpX:
        tmp.add(a[1])
        #print('i:{}, tmp'.format(i), tmp)
    elif a[1] == i:
      if a[0] not in tmpX:
        tmp.add(a[0])
        #print('i:{}, tmp'.format(i), tmp)
  tmpX = tmpX | tmp
  #print('tmpX', tmpX)
  # 再帰
  for t in tmp:
    mySearch(t)

def main():
  global tmpX
  ans = [None]*N
  
  for i in range(N):
    tomo = set()# 友達リスト
    for a in A:
      if a[0] == i+1:
        tomo.add(a[1])
      elif a[1] == i+1:
        tomo.add(a[0])
        
    block = set()# ブロックリスト
    for c in C:
      if c[0] == i+1:
        block.add(c[1])
      elif c[1] == i+1:
        block.add(c[0])
    
    tmpX = set()
    mySearch(i+1)
    #print('tmpX',tmpX, tomo, block)
    ans[i] = len(tmpX - tomo - block - set([i+1]))
    #print('ans[{}]'.format(i), tmpX - tomo - block)
  print(*ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000)

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())
friends=[0]*n
uf = UnionFind(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
 
nowlist=list(uf.all_group_members().values())
 
koho=[0]*n
group=[0]*n
number=1
for nl in nowlist:
    ng=len(nl)
    for nnl in nl:
        koho[nnl]=ng
        group[nnl]=number
    number+=1
 
for i in range(k):
    c, d = map(int,input().split())
    if group[c-1]==group[d-1]:
        koho[c-1]-=1
        koho[d-1]-=1
 
for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m, k = map(int, input().split())
ff = [[] for _ in range(n+1)]
bl = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    ff[a].append(b)
    ff[b].append(a)
for _ in range(k):
    c, d = map(int, input().split())
    bl[c].append(d)
    bl[d].append(c)
    
ans = []
    
for i in range(1, n+1):
    st = i
    visited = [0 for _ in range(n+1)]
    visited[i] = 1
    que = deque([])
    que.append(i)
    kamo = []
    while que:
        p = que.popleft()
        for idx in ff[p]:
            if visited[idx] == 0:
                visited[idx] = 1
                que.append(idx)
                if (idx not in ff[st]) and (idx not in bl[st]):
                    kamo.append(idx)
    ans.append(len(kamo))
    
mae = [str(an) for an in ans]
mae = " ".join(mae)
print(mae)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#def find_friend(tree_node, target):
#    for friend in tree_node.friends:
#        if target in friend.friend_numbers:
#            return True
#
#    flags = []
#    for friend in tree_node.friends:
#        flags.append(find_friend(friend, target))
#    if True in flags:
#        return True
#    return False

def display(node):
        print('----')
        print('val: {}'.format(node.val))
        print('friend_numbers: {}'.format(node.friend_numbers))
        print('block_numbers: {}'.format(node.block_numbers))

def find_friend(root, target):
    queue = [root]
    already_list = [root.val]
    while len(queue) > 0:
        node = queue.pop(0)
        if target in node.friend_numbers:
            return True
        
        for friend in node.friends:
            if friend.val not in already_list:
                queue.append(friend)
                already_list.append(friend.val)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.friends = []
        self.friend_numbers = []
        self.blocks = []
        self.block_numbers = []
        self.candidate = []

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

AB = []
for m in range(M):
    [a, b] = [int(i) for i in input().split()]
    AB.append((a, b))

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

tree_nodes = {}
for i in range(1, N + 1):
    tree_node = TreeNode(i)
    tree_nodes[i] = tree_node

for (a, b) in AB:
    tree_nodes[a].friends.append(tree_nodes[b])
    tree_nodes[a].friend_numbers.append(b)
    tree_nodes[b].friends.append(tree_nodes[a])
    tree_nodes[b].friend_numbers.append(a)

for (c, d) in CD:
    tree_nodes[c].blocks.append(tree_nodes[d])
    tree_nodes[c].block_numbers.append(d)
    tree_nodes[d].blocks.append(tree_nodes[c])
    tree_nodes[d].block_numbers.append(c)

candidates = []
for k, v in tree_nodes.items():
    # 友達候補を探す
    candidate = 0
    for n in range(1, N + 1):
        if n == k:
            continue
        if n in v.friend_numbers:
            continue
        if n in v.block_numbers:
            continue

        # nさんへの友達経路があるか探索
        flag = find_friend(v, n)
        if flag:
            candidate += 1
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

ans = ''
for candidate in candidates:
    ans += str(candidate)
    ans += ' '

print(ans[:len(ans)-1])

Submission status: Time Limit Exceeded

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

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')
for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1
#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

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

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]

def resolve():
    n,m,k=list(map(int,input().strip().split()))

    uf = UnionFind(n)

    res=[[] for i in range(n)]
    frd=[[] for i in range(n)]
    blk=[[] for i in range(n)]

    for i in range(m):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        uf.union(a,b)
        frd[a].append(b)
        frd[b].append(a)
    
    for i in range(k):
        a,b=list(map(int,input().strip().split()))
        a-=1
        b-=1
        #blk[a].append(b)
        #blk[b].append(a)
        frd[a].append(b)
        frd[b].append(a)
    
    rescnt=[]

    for i in range(n):
        ri=0
        for x in uf.members(i):
            if x==i:
                continue
            if x in frd[i]:
                ri+=0
            else:
                ri+=1
        rescnt.append(str(ri))
        ##rescnt.append(str(n-uf.size(i)-len(blk[i])))
    
    print(" ".join(rescnt))

resolve()

Submission status: Time Limit Exceeded

Solution code:
import re
n,m,k=map(int,input().split())
friend=[set() for _ in range(n+1)]
block=[set([i]) for i in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    friend[a].add(b)
    friend[b].add(a)

for _ in range(k):
    c,d=map(int,input().split())
    block[c].add(d)
    block[d].add(c)

ans=[]
friend_kouho=[friend[i] for i in range(n+1)]
#print(friend_kouho)
#print(block)
for i in range(1,n+1):
#    print("friend_kouho:"+str(friend_kouho))
    friend_assume=friend_kouho[i]
    temp=set()
    while(True):
        for j in list(friend_assume):
            temp = temp | friend[j]

#        print(i,temp,friend_assume,friend[i])

        if(len(temp)==0):
            ans.append(0)
            break
        elif(len(temp - friend_assume)>0):
            friend_assume = friend_assume | temp
        elif(len(temp - friend_assume)==0):
            friend_kouho[i] = friend_assume - block[i] - friend[i]
            ans.append(len(friend_kouho[i]))
            break
print(re.sub('[\[\],]','',str(ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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())
AB = [list(map(int, input().split())) for _ in range(m)]
CD = [list(map(int, input().split())) for _ in range(k)]

fre = defaultdict(list)
for a, b in AB:
  fre[a - 1].append(b - 1)
  fre[b - 1].append(a - 1)

blo = defaultdict(list)
for c, d in CD:
  blo[c - 1].append(d - 1)
  blo[d - 1].append(c - 1)

#print(fre)
#print(blo)

uf = UnionFind(n)
for a, b in AB:
  uf.union(a-1, b-1)
#print(uf)
print(*[len(set(uf.members(i)) - set(fre[i]) - set(blo[i])) - 1 for i in range(n)])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,M,K = map(int,input().split())
friend = [list(map(int,input().split())) for _ in range(M)]
block = [list(map(int,input().split())) for _ in range(K)]

g = [[False]*(N+1) for _ in range(N+1)]
for i in friend:
    g[i[0]][i[1]] = True
    g[i[1]][i[0]] = True


b = [[False]*(N+1) for _ in range(N+1)]
for i in block:
    b[i[0]][i[1]] = True
    b[i[1]][i[0]] = True
    

stack=deque()

ans = []
for i in range(1,N+1):
    cnt = 0
    visited = [0] * (N+1)
    visited[i] = 1 
    stack.append(i)
    while stack:
        n = stack.pop()
        for j in range(1,N+1):
            if g[n][j] and visited[j]==0:
                stack.append(j)
                visited[j] = 1
                if g[i][j] == False and b[i][j]==False:
                    cnt+=1
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#import re
import sys
input = sys.stdin.readline
#import heapq
#import bisect
from collections import deque
#import math

def main():
    n, m, k = map(int, input().split())
    F = [[] for i in range(n)]
    B = [[] for i in range(n)]
    for i in range(m):
        i, j = map(int, input().split())
        i -= 1
        j -= 1
        F[i].append(j)
        F[j].append(i)
    for i in range(k):
        i, j = map(int, input().split())
        i -= 1
        j -= 1
        B[i].append(j)
        B[j].append(i)
    ANS = [0] * n
    for i in range(n):
        ans = 0
        l = [0] * n
        l[i] = 1
        Q = deque(F[i])
        while(Q):
            check = Q.pop()
            if l[check] == 1: continue
            else:
                l[check] = 1
                Fnew = F[check]
                if check not in F[i]:
                    if check not in B[i]: 
                        ans += 1
                Q.extend(Fnew)
        
        ANS[i] = ans
    print(*ANS)




    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, K = lr()
    fri = [[] for _ in range(N)]
    for i in range(M):
        a, b = lr()
        fri[a-1].append(b-1)
        fri[b-1].append(a-1)
    blo = [[] for _ in range(N)]
    for i in range(K):
        c, d = lr()
        blo[c-1].append(d-1)
        blo[d-1].append(c-1)

    can = [[] for _ in range(N)]
    from collections import deque
    for i in range(N):
        vis = [False for _ in range(N)]
        s = deque()
        s.append(i)
        while len(s) > 0:
            v = s.pop()
            vis[v] = True
            for j in fri[v]:
                if vis[j]:
                    continue
                s.append(j)
                if j not in fri[i] and j not in blo[i] and j not in can[i]:
                    can[i].append(j)
    ans = []
    for i in range(N):
        ans.append(len(can[i]))
    print(*ans, sep=' ')
resolve()

Submission status: Time Limit Exceeded

Solution code:
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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N+1)

fb = [[False]*(N+1) for _ in range(N+1)]

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

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

res = [0]*(N+1)

gp = list(uf.all_group_members().values())

for g in gp:
    for i in range(len(g)):
        for j in range(i+1, len(g)):
            n = g[i]
            m = g[j]
            if fb[n][m]:
                continue
            else:
                res[n] += 1
                res[m] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N,M,K = map(int, input().split())
ans = [0]*N
table = [[] for i in range(N)]
visited = [0]*N
block = [[] for i in range(N)]
groups = [[] for i in range(N)]

for i in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    table[a].append(b)
    table[b].append(a)
for i in range(K):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    block[c].append(d)
    block[d].append(c)



for i in range(N):
    if visited[i] == 0:
        Q = deque()
        Q.append(i)
        visited[i] = 1
        group = deque()
        group.append(i)
        n = 1
        while Q:
            x = Q.popleft()
            for y in table[x]:
                if visited[y] == 0:
                    Q.append(y)
                    visited[y] = 1
                    n += 1
                    group.append(y)
        for x in group:
            groups[x] = set(group)
            ans[x] += n-len(table[x])-1

for i in range(N):
    temp = set(block[i]) & groups[i]
    ans[i] -= len(temp)
#    print(temp,ans[i])

"""
        n = len(group)
        for i in range(n):
            x = group[i]
            ans[x] += n - len(table[x]) - 1
            for j in range(i + 1, n):
                y = group[j]
                if y in block[x]:
                    ans[x] -= 1
                    ans[y] -= 1
        for x in group:
            ans[x] += n-len(table[x])-1
"""
print(" ".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

n, m, k = [int(i) for i in input().split()]

def root(x):
  if roots[x] == x:
    return x
  roots[x] = root(roots[x]) 
  return roots[x]

roots = [i for i in range(n)]
f = {}
for i in range(m):
  a, b = [int(j) for j in input().split()]
  a -= 1
  b -= 1
  f[a] = f.get(a, set()) | set([b])
  f[b] = f.get(b, set()) | set([a])
  
  ra = root(a)
  rb = root(b)
  if ra != rb:
    if ra < rb:
      roots[ra] = rb
    else:
      roots[rb] = ra
  
e = {}
for j in range(k):
  c, d = [int(j) for j in input().split()]
  c -= 1
  d -= 1
  e[c] = e.get(c, set([])) | set([d])
  e[d] = e.get(d, set([])) | set([c])
  

root_d = {}
rs = [root(i) for i in range(n)]
for idx, r in enumerate(rs):
  root_d[r] = root_d.get(r, set([])) | set([idx])

ans = []
for i in range(n):
  r = root_d[rs[i]].copy()
  r.remove(i)
  if i in f:
    r -= f[i]
  if i in e:
    r -= e[i]
  ans.append(str(len(r)))
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

n, m, k = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(m)]
cd = [tuple(map(int,input().split())) for i in range(k)]
es1 = [[] for i in range(n)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    es1[a].append(b)
    es1[b].append(a)

es2 = [[] for i in range(n)]
for i, (c,d) in enumerate(cd):
    c,d = c-1,d-1
    es2[c].append(d)
    es2[d].append(c)

ans = [0]*n

for i in range(n):
    visited = [False] * n
    i_good = es1[i]
    i_bad = es2[i]
    visited
    queue = deque()
    queue.extend(i_good)

    while len(queue):
        next_ = queue.pop()
        if visited[next_] == False:
            if (not next_ in i_good) and (not next_ in i_bad):
                ans[i] += 1
            visited[next_] = True
            queue.extend(es1[next_])

    ans[i] -= 1
    if ans[i] < 0:
        ans[i] = 0

print(*ans, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
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 LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,M,K = MI()
	frend = [[] for _ in range(N)]
	block = [[] for _ in range(N)]
	for _ in range(M):
		A,B = map(int1, sys.stdin.readline().split())
		frend[A].append(B)
		frend[B].append(A)
	group = []
	que = deque()
	cnt = 0
	N_ch = [-1]*N
	g = -1
	while cnt < N:
		for i in range(N):
			if N_ch[i]==-1 :
				que.append(i)
				g+=1
				N_ch[i]=g
				group.append(0)
				break
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group[g]+=1
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g

	for _ in range(K):
		C,D = map(int1, sys.stdin.readline().split())
		if(N_ch[C]==N_ch[D]):
			block[C].append(D)
			block[D].append(C)

	ans_v = []
	for i in range(N):
		ans = group[N_ch[i]]-len(frend[i])-len(block[i])
		ans_v.append(ans-1)
	printH(ans_v)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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())
SNS = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1
UF = UnionFind(N+1)
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    q = deque()
    j = 1
    memo = [False]*(N+1)
    while j <= N:
      if SNS[i][j] == 1:
        q.append(j)
      j += 1
    while q:
      j = q.pop()
      seen[j] = True
      memo[j] = True
      UF.union(i, j)
      k = 1
      while k <= N:
        if SNS[j][k] == 1 and not memo[k]:
          q.append(k)
        k += 1
  i += 1
ans = ""
i = 1
while i <= N:
  c = -1
  for j in UF.members(i):
    if SNS[i][j] == 0:
      c += 1
  ans += "%d "%c
  i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)
N,M,K=map(int,input().split())
F=[set() for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    F[a-1].add(b-1)
    F[b-1].add(a-1)
B=[set() for i in range(N)]
for _ in range(K):
    c,d=map(int,input().split())
    B[c-1].add(d-1)
    B[d-1].add(c-1)

def dps(i, j, c):
    s=0
    con=False
    for f in F[j]:
        if f not in c:
            con=True
            c.add(f)
            if f not in F[i] and f not in B[i]:
                s+=1
            s+=dps(i,f,c)
    if not con:
        return 0
    else:
        return s
for i in range(0,N):
    checked=set([i])
    print(dps(i, i, checked), end=" ")

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    "https://www.kumilog.net/entry/union-find"
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

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


uf = UnionFind(N)
fr = {}
for _ in range(M):
    a, b = map(int, input().split(" "))
    a -= 1
    b -= 1
    uf.union(a, b)
    if fr.get(a) is not None:
        fr[a].append(b)
    else:
        fr[a] = [b]

    if fr.get(b) is not None:
        fr[b].append(a)
    else:
        fr[b] = [a]

bl = {}
for _ in range(K):
    c, d = map(int, input().split(" "))
    c -= 1
    d -= 1
    if bl.get(c) is not None:
        bl[c].append(d)
    else:
        bl[c] = [d]

    if bl.get(d) is not None:
        bl[d].append(c)
    else:
        bl[d] = [c]


for i in range(N):
    s = uf.get_size(i) - 1

    for b in bl.get(i, []):
        if uf.is_same(i, b):
            s -= 1

    s -= len(fr.get(i, []))
    print(s)