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:
N, M, K = map(int, input().split())
friend_mat = [[False] * N for _ in range(N)]
friends = [set() for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    friend_mat[a - 1][b - 1] = True
    friend_mat[b - 1][a - 1] = True
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)

block_mat = [[False] * N for _ in range(N)]
blocks = [set() for _ in range(N)]
for i in range(K):
    c, d = map(int, input().split())
    block_mat[c - 1][d - 1] = True
    block_mat[d - 1][c - 1] = True
    blocks[c - 1].add(d - 1)
    blocks[d - 1].add(c - 1)

cands_mat = [[-1] * N for _ in range(N)]
cands = [0] * N
for i in range(N):
    q = [i]
    cands_mat[i][i] = 0
    while True:
        n0 = q.pop(0)
        for n in friends[n0]:
            if cands_mat[i][n] < 0:
                q.append(n)
                cands_mat[i][n] = cands_mat[i][n0] + 1
        if len(q) == 0:
            break

    for j in range(N):
        step = cands_mat[i][j]
        if step >= 2 and not (i == j or friend_mat[i][j] or block_mat[i][j]):
            cands[i] += 1

print(" ".join(str(c) for c in cands))

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())
F = [input().split() for i in range(M)]
bdict = {}
for i in range(K):
  a,b = map(int,input().split())
  a = a - 1
  b = b - 1
  if a not in bdict:
    bdict[a] = set()
  if b not in bdict:
    bdict[b] = set()
  bdict[a].add(b)
  bdict[b].add(a)
u = UnionFind(N)

fdict = {}
for f in F:
  a = int(f[0])-1
  b = int(f[1])-1
  u.union(a, b)
  if a not in fdict:
    fdict[a] = set()
  if b not in fdict:
    fdict[b] = set()
  fdict[a].add(b)
  fdict[b].add(a)
ans = [0]*N
import copy
for r in u.roots():
  mems = set(u.members(r))
  for i in mems:
    memstmp = copy.deepcopy(mems)
    if i in bdict:
      memstmp = memstmp - bdict[i]
    if i in fdict:
      memstmp = memstmp - fdict[i]
    ans[i] = len(memstmp)-1
fin = ""
for a in ans:
  fin += str(a) + " "
print(fin[:-1])

Submission status: Time Limit Exceeded

Solution code:
def inputs(): return (int(x) for x in input().split())
N,M,K = inputs()
f = {i:[] for i in range(N)}
b = {i:[] for i in range(N)}
ans = [0]*(N)
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    f[x-1].append(y-1)
    f[y-1].append(x-1)
for _ in range(K):
    x,y = inputs()
    b[x-1].append(y-1)
    b[y-1].append(x-1)
for i in range(N):
    visited =visited = {i: False for i in range(N)}
    stk = [(i,-1,0)]
    while stk:
        v,p,l = stk.pop()
        if visited[v]:
            continue
        visited[v] = True
        if 1<l and not v in b[i] and not v in f[i]:
            ans[i]+=1
        for u in f[v]:
            if u !=p:
                stk.append((u,v,l+1))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
class UnionFind():
    def __init__(self, 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
n,m,k = map(int,input().split())
uf = UnionFind(n)
#初期化したら友達関係を受け取ってufを形成していく union
friend = [0]*n
# 友達が何人いるかも必要
for i in range(m):
    a,b = map(int,input().split())
    friend[a-1] += 1
    friend[b-1] += 1
    uf.union(a-1,b-1)
# uf が完成したら,c,d を受け取り、parentの値が同じならblock[c],bloc[d]+=1をする
block = [0]*n
for j in range(k):
    c,d = map(int,input().split())
    if uf.find(c-1) == uf.find(d-1):
        block[c-1]+=1
        block[d-1]+=1
"""
print(uf.parents)
print(block)
print(friend)"""
for i in range(n):
    #print(abs(uf.parents[uf.find(i)]),":",i)
    print(abs(uf.parents[uf.find(i)]) - 1 - friend[i] - block[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from queue import Queue
N,M,K=map(int, input().split())
F={}
B={}
for i in range(N):
  F[i]=[]
  B[i]=[]
for i in range(M):
  a,b=map(int, input().split())
  a-=1
  b-=1
  F[a].append(b)
  F[b].append(a)
for i in range(K):
  c,d=map(int, input().split())
  c-=1
  d-=1
  B[c].append(d)
  B[d].append(c)
  
def Adj(u):
  adj=[]
  for v in range(N):
    if F[u,v]==1 and v!=u:
    	adj.append(v)
  return adj    

def BFS():
  cands=[]
  for s in range(N):
    cand=[]
    visited=[s]
    #main関数でスタートを塗りつぶすのを忘れないように
    Q=Queue()
    Q.put(s)
    while not Q.empty():
      u=Q.get()
      if u!=s and u not in B[s] and u not in F[s]:
        cand.append(u)
      for v in F[u]:  
        if v not in visited:
          Q.put(v)
          visited.append(v)
    cands.append(str(len(cand)))
  print(' '.join(cands))
BFS()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

class UnionFind:
    def __init__(self, N):
        # negative value: represents the root of a tree; its absolute value is the size of the tree
        # positive value: the parent's index
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: # v is a root
            return v
        else:
            # path compression: reconnect v to the root
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) # the root of the tree including vertex u
        s2 = self.find(v) # the root of the tree including vertex v
        
        if s1 == s2: # u and v is in the same tree
            return False
        
        if self.rank[s1] > self.rank[s2]: # the tree including u is taller
            self.vertices[s1] += self.vertices[s2] # update the size of the bigger tree
            self.vertices[s2] = s1
        else: # the tree including v is taller
            self.vertices[s2] += self.vertices[s1] # update the size of the bigger tree
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

N, M, K = map(int, input().split())
uf_fr = UnionFind(N)
n_friends = [0] * N
brocks = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    n_friends[a] += 1
    n_friends[b] += 1
    uf_fr.union(a, b)
for _ in range(K):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    brocks[a].append(b)
    brocks[b].append(a)
clusters = [[] for _ in range(N)]
for i in range(N):
    clusters[uf_fr.find(i)].append(i)
print(*[len(set(clusters[uf_fr.find(i)]) - set(brocks[i])) - 1 - n_friends[i] for i in range(N)])

Submission status: Time Limit Exceeded

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


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

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

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

not_see = [set() for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = [set([i]) for i in range(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
        self.group[x] = self.group[x] | self.group[y]
        self.group[y] = set()
    def size(self, x):
        return -self.parents[self.find(x)]

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

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

    def group_count(self):
        return len(self.roots())
u = UnionFind(n+1)
li = []
adjacent_list = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
    li.append([a,b])
for i in range(k):
    a,b = map(int, input().split())
    li.append([a,b])
li.sort()
index = 0
ans_li = [-1 for i in range(n+1)]
for i in range(1,n+1):
    ans_li[i] += u.size(u.find(i))
    group = u.group[u.find(i)]
    while index < k+m and li[index][0] == i:
        if li[index][1] in group:
            ans_li[i] -= 1
            ans_li[li[index][1]] -= 1
        index += 1
for i in range(1,n+1):
    print(ans_li[i], end = " ")

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

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

friend = np.array([[10 ** 10 for i in range(n)] for j in range(n)])
for i in range(n):
  friend[i][i] = 0

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

dist = shortest_path(friend)

for i in range(k):
  c, d = map(int, input().split())
  dist[c - 1][d - 1] = dist[d - 1][c - 1] = -1

ans = np.sum((dist < 10 ** 10) & (dist > 1), axis = 1)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    N, M, K = map(int, sys.stdin.readline().split())

    F = [set() for _ in range(N)]
    B = [set() for _ in range(N)]
    for m in range(M):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a - 1, b - 1
        F[a].add(b)
        F[b].add(a)

    for k in range(K):
        c, d = map(int, sys.stdin.readline().split())
        c, d = c - 1, d - 1
        B[c].add(d)
        B[d].add(c)

    D = defaultdict(set)
    parents = [-1] * N
    visited = set()
    for s in range(N):
        if s in visited:
            continue

        stack = [s]
        D[s].add(s)
        while stack:
            n = stack.pop()
            visited.add(n)
            parents[n] = s
            for to in F[n]:
                if to in visited:
                    continue
                D[s].add(to)
                stack.append(to)

    #print(1 / 0)
    ans = [0] * N
    #print(D)
    for i in range(N):
        #print(D[parents[i]] - F[i] - B[i] - {i}, F[i], B[i])
        ans[i] = len(D[parents[i]] - F[i] - B[i] - {i})

    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

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)
	groups = []
	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 = []
				break
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group.append(i)
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g
			if len(que)==0 : groups.append(group)

	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 = len(groups[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:
n, m, k = map(int, input().split())

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


def append_candidate(a, b):
    if b not in candidate[a] and b not in friend[a] and b != a:
        candidate[a].append(b)
    if a not in candidate[b] and a not in friend[b] and a != b:
        candidate[b].append(a)


def update_candidate(a, b):
    for af in friend[a]:
        append_candidate(af, b)
        for bf in friend[b]:
            append_candidate(af, bf)
        for bc in candidate[b]:
            append_candidate(af, bc)

    for ac in candidate[a]:
        append_candidate(ac, b)
        for bf in friend[b]:
            append_candidate(ac, bf)
        for bc in candidate[b]:
            append_candidate(ac, bc)


for i in range(m):
    a, b = map(int, input().split())

    if a in candidate[b]:
        candidate[b].remove(a)
    if b in candidate[a]:
        candidate[a].remove(b)

    friend[a].append(b)
    friend[b].append(a)

    update_candidate(a, b)
    update_candidate(b, a)

for i in range(k):
    c, d = map(int, input().split())
    if c in candidate[d]:
        candidate[d].remove(c)
    if d in candidate[c]:
        candidate[c].remove(d)

print(' '.join(str(len(candidate[i])) for i in range(1, n+1)))

Submission status: Time Limit Exceeded

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

N, M , K = [int(x) for x in input().split()]
AB = []
G_F = [deque([]) for _ in range(N)]
G_B = [deque([]) for _ in range(N)]
G_F_s = [set() for _ in range(N)]
G_B_s = [set() for _ in range(N)]
for _ in range(M):
    AB = [int(x) for x in input().split()]
    G_F[AB[0] - 1].append(AB[1] - 1)
    G_F[AB[1] - 1].append(AB[0] - 1)
    G_F_s[AB[0] - 1].add(AB[1] - 1)
    G_F_s[AB[1] - 1].add(AB[0] - 1)

CD = []
for _ in range(K):
    CD = [int(x) for x in input().split()]

    G_B[CD[0] - 1].append(CD[1] - 1)
    G_B[CD[1] - 1].append(CD[0] - 1)
    G_B_s[CD[0] - 1].add(CD[1] - 1)
    G_B_s[CD[1] - 1].add(CD[0] - 1)

ans = 0
from collections import deque
G_F = deque(G_F)
G_B = deque(G_B)

# グラフの作成(無向グラフでは#を消す)

time = 0
arrive_time = [-1] * (N) # 到着時刻

# 深さ優先探索
def dfs(v, graph):
    global time
    time += 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w) 
        else:
            stack.pop()          
    return arrive_time
import copy
ans = [0] * N
for i in range(N - 1):
    for j in range(i + 1, N):
        arrive_time = [-1] * N
        if j in G_B_s[i] or j in G_F_s[i]:
            continue
        graph = copy.deepcopy(G_F)
        arrive_time = dfs(i, graph)
        if arrive_time[j] > 0:
            ans[i] += 1
            ans[j] += 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def connected(v,g,n):
    tansaku = [False for i in range(n+1)]  # 探索済みかを表す
    S = g[v][:]
    tansaku[v] = True
    list_connected = []
    
    while(len(S) >= 1):
        nei_v = S.pop(0)  # 先頭の要素を取得
        if tansaku[nei_v] is False:
            tansaku[nei_v] = True  # 探索済みにする
            list_connected.append(nei_v)
            S.extend(g[nei_v])
    
    return list_connected
    

n,m,k = map(int,input().split())
g = [[] for i in range(n+1)]

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

ng = [[] for i in range(n+1)]
for i in range(k):
    c,d = map(int,input().split())
    ng[c].append(d)
    ng[d].append(c)

for i in range(1,n+1):
    v_connected = connected(i,g,n)
    num_friend = len(g[i])
    ng_connected = len(set(v_connected) & set(ng[i]))
    # print(i,[v_connected,num_friend,ng_connected])
    print(len(v_connected) - num_friend - ng_connected, end='')
    if i != n:
        print(" ", end="")

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M, K = map(int, input().split())
    friendship = [set() for _ in range(N + 1)]
    uf_tree = UnionFind(N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        friendship[a].add(b)
        friendship[b].add(a)
        if not uf_tree.same(a, b):
            uf_tree.union(a, b)
    block = [set() for _ in range(N + 1)]
    for _ in range(K):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    
    ans = [0] * (N + 1)
    searched = [False] * (N + 1)
    for i in range(1, N + 1):
        if searched[i]:
            continue
        member = uf_tree.members(i)
        for j in member:
            searched[j] = True
        len_member = len(member)
        for s in range(len_member - 1):
            for t in range(s + 1, len_member):
                if member[t] in block[member[s]]:
                    continue
                if member[t] in friendship[member[s]]:
                    continue
                ans[member[s]] += 1
                ans[member[t]] += 1
    print(' '.join(map(str, ans[1:])))


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F



def make_cluster(N, friend):
    import queue
    C = []
    already = [False] * N
    for i in range(N):
        if already[i]:
            continue
        already[i] = True
        s = {i}
        q = queue.Queue()
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        C.append(s)

    return C


def main():
    import queue
    N, M, K = read_values()

    friend = [set() for _ in range(N)]
    for _ in range(M):
        a, b = read_index()
        friend[a].add(b)
        friend[b].add(a)
    
    block = [set() for _ in range(N)]
    for _ in range(K):
        a, b = read_index()
        block[a].add(b)
        block[b].add(a)

    already = [False] * N
    C = [0] * N
    for i in range(N):
        if already[i]:
            continue
        s = {i}
        q = queue.Queue()
        already[i] = True
        q.put(i)
        while not q.empty():
            k = q.get()
            out = friend[k]
            for l in out:
                if already[l]:
                    continue
                s.add(l)
                q.put(l)
                already[l] = True
        for j in s:
            C[j] = len(s.difference(block[j]))
    res = [str(C[i] - len(friend[i]) - 1) for i in range(N)]
    print(" ".join(res))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

N, M, K = map(int, input().split())
# F = [list(map(int, input().split())) for _ in range(M)]
# B = [list(map(int, input().split())) for _ in range(K)]

F = defaultdict(set)
for _ in range(M):
    u, v = map(int, input().split())
    F[u].add(v)
    F[v].add(u)
B = defaultdict(set)
for _ in range(K):
    u, v = map(int, input().split())
    B[u].add(v)
    B[v].add(u)

res = []
for i in range(N):
    cand = 0
    visited = [0]*N
    q = deque()
    q.append((i+1, 0))
    visited[i] = 1

    while q:
        curNode, lv = q.popleft()
        for node in F[curNode]:
            if visited[node-1] == 0:
                visited[node-1] = 1
                q.append((node, lv+1))
                if lv >= 1 and i+1 not in B[node]:
                    cand += 1

    res.append(cand)

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

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)
	groups = []
	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 = []
				break
		while len(que)>0:
			i = que[-1]
			cnt += 1
			que.pop()
			group.append(i)
			fr = frend[i]
			for f in fr:
				if(N_ch[f]==-1):
					que.appendleft(f)
					N_ch[f]=g
			if len(que)==0 : groups.append(group)

	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 = len(groups[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:
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 unite(self,x,y): #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 same(self,x,y):#xとyが同じグループにいるか判定
        return self.find(x)==self.find(y)
    
    def members(self,x):#xと同じグループのメンバーを列挙
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    
    def size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        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):#print()での表示用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m,k=map(int,input().split())
    F=[set() for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        F[a].add(b)
        F[b].add(a)

    B=[set() for _ in range(n)]
    for _ in range(k):
        c,d=map(int,input().split())
        c-=1
        d-=1
        B[c].add(d)
        B[d].add(c)

    
    uf=UnionFind(n)
    for i in range(n):
        for f in F[i]:
            uf.unite(i,f)
    
     
    cnt=[0]*n
    A=uf.all_group_members()
    for r in A:
        M=set(A[r])
        for m in M:
            for m2 in M:
                if m2 not in F[m] and m2 not in B[m] and m!=m2:
                    cnt[m]+=1
    print(*cnt)
   
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


# xとyの属する集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        # sizeの大きいほうがx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y]
        par[y] = x
        return True


# xとyが同じ集合に属するかの判定
def same(x, y):
    return find(x) == find(y)


# xが属する集合の個数
def size(x):
    return -par[find(x)]


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

# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

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

not_see = [set() for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    unite(a, b)
    friend[a][b] = 1
    friend[b][a] = 1
    if same(a, b):
        not_see[a].add(b)
        not_see[b].add(a)

for c, d in cd:
    c -= 1
    d -= 1
    block[c][d] = 1
    block[d][c] = 1
    if same(c, d):
        not_see[c].add(d)
        not_see[d].add(c)

for i in range(n):
    print(size(i) - len(not_see[i]) - 1)