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:
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.pop()
        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:
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())
G = UnionFind(N)

friends = {i:0 for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    friends[a-1] += 1
    friends[b-1] += 1
    G.union(a-1, b-1)

# ブロック関係にあったら友達と考える
for i in range(K):
    c, d = map(int, input().split())
    if G.same(c-1, d-1):
        friends[c-1] += 1
        friends[d-1] += 1

ans = []
for i in range(N):
    ans.append(len(G.members(i)) - friends[i] - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    AB = [tuple(map(int, ab)) for ab in map(str.split, args[1:1+m])]
    CD = [tuple(map(int, cd)) for cd in map(str.split, args[1+m:1+m+k])]

    friends = [set() for _ in range(n+1)]
    blocked = [set() for _ in range(n+1)]

    for a, b in AB:
        friends[a].add(b)
        friends[b].add(a)

    for c, d in CD:
        blocked[c].add(d)
        blocked[d].add(c)

    ret = [0]*(n+1)
    checked = set()
    for a in range(1, n+1):
        if a in checked:
            continue
        connected = set()
        stack = list(friends[a])
        while stack:
            b = stack.pop()
            checked.add(b)
            connected.add(b)
            stack.extend(friends[b]-checked)
        for i in connected:
            ret[i] += len(connected-friends[i]-blocked[i]) - 1

    return ' '.join(map(str, ret[1:]))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = []
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= conn
            conns.append(conn)

    res = []
    for i in range(n):
        suggestion_cnt = 0
        current_conn = list(filter(lambda x: i in x, conns))[0]
        res.append(len(current_conn - graph_f[i] - graph_b[i]) - 1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import deepcopy
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
Chains = []
seen = [False]*(N+1)
i = 1
while i <= N:
  if not seen[i]:
    seen[i] = True
    chain = deque()
    q = deque()
    j = 1
    while j <= N:
      if SNS[i][j] == 1:
        q.append(j)
      j += 1
    memo = [False]*(N+1)
    while q:
      j = q.pop()
      if not memo[j]:
        memo[j] = True
        seen[j] = True
        chain.append(j)
        k = 1
        while k <= N:
          if SNS[j][k] == 1:
            q.append(k)
          k += 1
    Chains.append(deepcopy(chain))
  i += 1
ans = [0] * (N+1)
for chain in Chains:
  l = len(chain)
  for hito in chain:
    n = 0
    for aite in chain:
      n += 0 if SNS[hito][aite] == 0 else 1
    ans[hito] = l - n -1
s = ""
i = 1
while i <= N:
  s += "%d "%ans[i]
  i += 1
print(s)

Submission status: Time Limit Exceeded

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())
AB = [list(map(int, input().split())) for i in range(M)]
CD = [list(map(int, input().split())) for i in range(K)]
G = UnionFind(N)

friends = {i:0 for i in range(N)}
for a, b in AB:
    friends[a-1] += 1
    friends[b-1] += 1
    G.union(a-1, b-1)

# ブロック関係にあったら友達と考える
for c, d in CD:
    if G.same(c-1, d-1):
        friends[c-1] += 1
        friends[d-1] += 1

ans = []
for i in range(N):
    ans.append(len(G.members(i)) - friends[i] - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = []
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= conn
            conns.append(conn)

    res = []
    for i in range(n):
        suggestion_cnt = 0
        current_conn = list(filter(lambda x: i in x, conns))[0]
        for j in range(n):
            if i == j:
                continue
            else:
                if j in current_conn and j not in graph_f[i] and j not in graph_b[i]:
                    suggestion_cnt += 1
        res.append(suggestion_cnt)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = dic[str(now_node)]
        for tgt in target:
            if uf[tgt-1] == -1:
                q.put(tgt)
                uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(1,N+1):
    if uf[i-1] == -1:
        # 連結判定
        leng = BFS(var, dic, i)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

A = [0 for _ in range(N)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
answer = [[] for _ in range(N)]

for a, b in AB:
  friend[a-1].append(b)
  friend[b-1].append(a)

for c, d in CD:
  block[c-1].append(d)
  block[d-1].append(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    if f not in block[root-1] and f not in friend[root-1] and f != root:
      if f not in answer[root-1]:
        answer[root-1].append(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import queue
import numpy as np
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [0]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    #uf[node-1] = ufid
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] != 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = dic[str(now_node)]
        for tgt in target:
            if uf[tgt-1] == 0:
                q.put(tgt)
    return leng

len_ls = []
var = 1
for i in range(1,N+1):
    if uf[i-1] == 0:
        # 連結判定
        leng = BFS(var, dic, i)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
n,m,k = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(m):
    a,b = map(int,input().split())
    cost[a-1][b-1] = 1
    cost[b-1][a-1] = 1

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

ans = [0]*n

for a in range(n):
  for b, c in enumerate(dijkstra(a,n,m,cost)):
    if c > 1 and c != float("inf") and block[a][b] == 0:
      ans[a] += 1

print(*ans)

Submission status: Time Limit Exceeded

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())
AB = [list(map(int, input().split())) for i in range(M)]
CD = [list(map(int, input().split())) for i in range(K)]
G = UnionFind(N)

friends = {i:set() for i in range(N)}
for a, b in AB:
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)
    G.union(a-1, b-1)

blocks = {i:set() for i in range(N)}
for c, d in CD:
    blocks[c-1].add(d-1)
    blocks[d-1].add(c-1)

ans = []
for i in range(N):
    ans.append(len(set(G.members(i)) - friends[i] - blocks[i]) - 1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


friendship = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if a in friendship.keys():
        friendship[a].append(b)
    else:
        friendship[a] = [b]
        
    if b in friendship.keys():
        friendship[b].append(a)
    else:
        friendship[b] = [a]
        
block = {}
for j in range(k):
    c, d = list(map(int, input().split()))
    if c in block.keys():
        block[c].append(d)
    else:
        block[c] = [d]
        
    if d in block.keys():
        block[d].append(c)
    else:
        block[d] = [c]
        
ans = [0] * n
for i in range(n):
    person = i+1
    checked_person = set()
    checked_person.add(person)
    if person in friendship.keys():
        candidate = deque(friendship[person])
        while len(candidate)>0:
            c = deque.popleft(candidate)
            checked_person.add(c)
            if c not in friendship[person]:
                if person in block.keys():
                    if c not in block[person]:
                        ans[i] += 1
                else:
                    ans[i] += 1
            if c in friendship.keys():
                for p in friendship[c]:
                    if p not in checked_person and p not in candidate:
                        candidate.append(p)
    else:
        continue
                
answer = ''
for i in range(len(ans)):
    answer += str(ans[i])
    if i != n-1:
        answer += ' '
            
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = (int(x) for x in input().split())
#n_f = []
#n_b = []
#for i in range(n):
#    n_f.append(0)
#    n_b.append(0)

#A = []
#B = []
F = [[] for i in range(n)]
for i in range(m):
    a,b = (int(x) for x in input().split())
    #A.append(a)
    #B.append(b)
    F[a-1].append(b-1)
    F[b-1].append(a-1)
    #n_f[a-1] += 1
    #n_f[b-1] += 1
#C = []
#D = []
#B = [[]]*n
B = [[] for i in range(n)]
for i in range(k):
    a,b = (int(x) for x in input().split())
    #C.append(a)
    #D.append(b)
    B[a-1].append(b-1)
    B[b-1].append(a-1)

#print(F)
tansaku = [False] * n
#vers = [[] for i in range(n)]
con = [-1] * n
counts = []
con_count = 0

for i in range(n):
    if tansaku[i]: continue
    tansaku[i] = True
    con[i] = con_count
    count = 1
    temp = [i]
    #ver = [i]
    while(len(temp)>0):
        this = temp[0]
        for j in F[this]:
        
            
            if tansaku[j] == True:
                continue
            else:
                tansaku[j] = True
                con[j] = con_count
                temp.append(j)
                #ver.append(j)
                count += 1
        temp = temp[1:]
    #print(ver)
    #for j in ver:
        #vers[j] = ver
    counts.append(count) 
    con_count += 1
    

#print(vers)
    
out = []
for i in range(n):
    #versi = vers[i]
    #count = len(versi)-1
    this_count = counts[con[i]] - 1
    for j in B[i]:
        #if j in versi:
        #    count -= 1
        if con[i] == con[j]:
            this_count -= 1
    out.append(str(this_count - len(F[i])))
print(" ".join(out))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = list(map(int, input().split()))
mat = [[0]*N for _ in range(N)]
C = {i:[] for i in range(N)}
for _ in range(M):
    a,b = list(map(int, input().split()))
    mat[a-1][b-1] = 1
    mat[b-1][a-1] = 1
    C[a-1].append(b-1)
    C[b-1].append(a-1)

for _ in range(K):
    c,d = list(map(int, input().split()))
    mat[c-1][d-1] = -1
    mat[d-1][c-1] = -1
    
new = [[0]*N for _ in range(N)]

def nex(cur, org):
    global prev
    for n in C[cur]:
        if org!=n and [cur,n] not in prev:
            prev.append([cur,n])
            prev.append([n,cur])
            if mat[cur][n]==1:
                if mat[org][n]==0:
                    new[org][n] = 1
                nex(n, org)
    return 0
    
for i in range(N):
    prev = []
    if sum(new[i])==0:
        nex(i, i)
print(' '.join([str(sum(new[i])) for i in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
graph_data=[[0]*N for _ in range(N)]
block_data=[[0]*N for _ in range(N)]
    
for _ in range(M):
    i,j=map(int,input().split())
    graph_data[i-1][j-1]=graph_data[j-1][i-1]=1
for _ in range(K):
    i,j=map(int,input().split())
    block_data[i-1][j-1]=block_data[j-1][i-1]=1

from collections import deque

def bfs(start, W):
    work_queue = deque([])
    visited = set()
    work_queue.append(start)
    visited.add(start)
    while work_queue:
        here = work_queue.popleft()
        for i, node in enumerate(W[here]):
            if node ==0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)

    return visited

ans=[0]*N
for i in range(N):
    for j in bfs(i,graph_data):
        if i==j:continue
        if graph_data[i][j]==0:
            ans[i]+=1
        if block_data[i][j]==1:
            ans[i]-=1
pri=''
for i in range(N):
    pri+=str(ans[i])
    if i!=N-1:
        pri+=' '
print(pri)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    count = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = [1 for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.count[y] += self.count[x]
            self.count[x] = self.count[y]
            return

    def getCount(self, x):
        self.count[x] = self.count[self.root(x)]
        return(self.count[x])


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

G = unionFind(N)
for a, b in AB:
    G.unite(a, b)

for i in range(N):
    G.root(i)

ans = [G.getCount(i) - 1 for i in range(N)]
# print(ans)
# print(G.count)
for a, b in AB:
    ans[a-1] -= 1
    ans[b-1] -= 1

for c, d in CD:
    if G.same(c, d):
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
def bfs(ind):
    kouho=friends[ind]
    for i in kouho:
        if sans[i]!=-1:
            continue
        sans[i]=sans[ind]
        l[sans[ind]].append(i)
        bfs(i)
n,m,k=list(map(int,input().split()))
f=[list(map(int,input().split())) for _ in range(m)]
friends=[set() for _ in range(n)]
friends_num=list(map(lambda x:len(x),friends))
bl=[list(map(int,input().split())) for _ in range(k)]
l=[[i] for i in range(n)]

for each in f:
    a,b=each
    friends[a-1].add(b-1)
    friends[b-1].add(a-1)

block=[set() for _ in range(n)]
for each in bl:
    a,b=each
    block[a-1].add(b-1)
    block[b-1].add(a-1)

sans=[-1 for _ in range(n)]
sans[0]=0
bfs(0)
for i in range(n):
    if sans[i]!=-1:
        continue
    sans[i]=i
    bfs(i)
ans=[0 for _ in range(n)]
for i in range(n):
    l[i]=set(l[i])


for i in range(n):
    tmp=l[sans[i]]-block[i]
    ans[i]=len(tmp)-len(friends[i])-1


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

Submission status: Time Limit Exceeded

Solution code:
"""
D
"""
import sys
input=sys.stdin.readline

def match_count(lst_1,lst_2):
    l_1,l_2=len(lst_1),len(lst_2)
    kkk=0
    zzz=0
    ttt=0
    while kkk<l_1:
        while zzz<l_2:
            if lst_1[kkk]>lst_2[zzz]:
                zzz+=1
                continue
            else:
                if lst_1[kkk]==lst_2[zzz]:
                    zzz+=1
                    ttt+=1
                break
        else:
            break
        kkk+=1
    return ttt

N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]
data1=[[] for i in range(N+1)]
data2=[[] for i in range(N+1)]
for A,B in AB:
    data1[A].append(B)
    data1[B].append(A)
for C,D in CD:
    data2[C].append(D)
    data2[D].append(C)
    
for i in range(N+1):
    data1[i].sort()
    data2[i].sort()
    
    
    
ans=[0]*(N+1)
flag=[0]*(N+1)
for i in range(1,N+1):
    if flag[i]==1:
        continue
    que=[i]
    H=[i]
    flag[i]=1
    while que:
        u=que.pop()
        for v in data1[u]:
            if flag[v]==0:
                flag[v]=1
                que.append(v)
                H.append(v)
                
    H.sort()
    for u in H:
        ans[u]=len(H)-len(data1[u])-match_count(H,data2[u])-1

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend, block = defaultdict(set), defaultdict(set)
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].add(b)
        friend[b].add(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    i = -1
    belonging = [-1] * n
    group = []
    next_search = []
    is_searched = [False] * n
    while not all(is_searched):
        if not next_search:
            for j, s in enumerate(is_searched):
                if not s:
                    next_search.append(j)
                    group.append(set())
                    i += 1
                    break
        j = next_search.pop()
        if is_searched[j]:
            continue
        is_searched[j] = True
        belonging[j] = i
        group[i].add(j)
        next_search += friend[j]
    suggestion = [len(group[belonging[i]].difference(friend[i]).difference(block[i])) - 1 for i in range(n)]
    print(*suggestion)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce
import sys
sys.setrecursionlimit(1000000)


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

    ary = []
    block = []

    for _ in range(N):
        ary.append(set())
        block.append(set())

    for _ in range(M):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        ary[A].add(B)
        ary[B].add(A)

    for _ in range(K):
        A, B = [int(v) - 1 for v in input().split()]
        if A == B:
            continue
        block[A].add(B)
        block[B].add(A)

    def dfs(n, closed):
        closed.add(n)
        for i in ary[n]:
            if not i in closed:
                dfs(i, closed)

    dp = [None] * N
    ans = []
    for i in range(N):
        if dp[i] is not None:
            continue
        s = set()
        dfs(i, s)
        for j in s:
            dp[j] = s

    for i in range(N):
        ans.append(len(dp[i] - block[i]) - len(ary[i]) - 1)
    ans = " ".join(map(str, ans))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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


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

[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

        flag = False
        # nさんが既に自分を友達候補にしていればOK
        if k in tree_nodes[n].candidate_numbers:
            flag = True
        else:
            # nさんへの友達経路があるか探索
            #flag = find_friend(v, n, [v.val])
            flag = find_friend(v, n)
        if flag:
            candidate += 1
            v.candidate_numbers.append(n)
        #print('{}の友達候補{}: {}'.format(k, n, flag))
    
    candidates.append(candidate)

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

#for k, v in tree_nodes.items():
#    display(v)

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