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:

#####

# import numpy as np
# from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128
from collections import defaultdict

#####

def getIntList(inp):
	return [int(_) for _ in inp]
	

from sys import stdin

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def st(x,y):
	return tuple(sorted([x,y]))

def getGroup(groups, i):
	if i not in groups:
		groups[i]=i
	return groups[i]
		
def main(inputs):
	n=int(inputs[0][0])
	m=int(inputs[0][1])
	k=int(inputs[0][2])

	fr=set()
	frSingle=defaultdict(set)
	for i in range(m):
		a=int(inputs[i+1][0])
		b=int(inputs[i+1][1])
		fr.add(st(a,b))
		frSingle[a].add(b)
		frSingle[b].add(a)
		
	bl=defaultdict(set)
	for i in range(k):
		a=int(inputs[i+1+m][0])
		b=int(inputs[i+1+m][1])
		bl[a].add(b)
		bl[b].add(a)
	
# 	print(fr)
# 	print(bl)
# 	print()
	
	groups={}
	members={}
	for i in range(1,n+1):
		groups[i]=i
		members[i]=set([i])
	for i0,i1 in fr:
		g0=getGroup(groups, i0)
		g1=getGroup(groups, i1)
		if g0==g1:
			continue
		if g0<g1:
			for m in members[g1]:
				groups[m]=g0
			members[g0].update(members[g1])
			members.pop(g1)
		else:
			for m in members[g0]:
				groups[m]=g1
			members[g1].update(members[g0])
			members.pop(g0)
	
# 	print(groups)
# 	print(members)
	
# 	print()
	for i0 in range(1,n+1):
		g=groups[i0]
		i1s=set(members[g])
		i1s.remove(i0)
		i1s=i1s-frSingle[i0]
		i1s=i1s-bl[i0]
# 		print(i0,i1s)
		num=len(i1s)
		print(num, end="")
		if i0<n: print(" ", end="")
	
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

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 = [set([]) 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] |= {b}
    brocks[b] |= {a}
clusters = {}
for i in range(N):
    clusters.setdefault(uf_fr.find(i), set([]))
    clusters[uf_fr.find(i)] |= {i}
print(*[len(clusters[uf_fr.find(i)] - 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)
    friend[a][b] = 1
    friend[b][a] = 1
    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
    not_see[c].add(d)
    not_see[d].add(c)

for i in range(n):
    ans = 0
    for j in range(n):
        if i == j:
            continue
        if j in not_see[i]:
            continue
        if same(i, j):
            ans += 1
    print(ans)

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 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())
u = UnionFind(n+1)
li = []
for i in range(m):
    a, b = map(int, input().split())
    u.union(a,b)
    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 = set(u.members(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 sys
input=sys.stdin.readline

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

tk=UnionFind(n)

kk=[[False] * n for _ in range(n)]

for _ in range(m):
    a,b=map(int, input().split())
    kk[a-1][b-1]=True
    kk[b-1][a-1]=True
    tk.union(a-1, b-1)

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

for i in range(n):
    ans=-1
    for j in range(n):
        if not kk[i][j] and tk.same(i, j):
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

n, m, k = map(int, input().split())
friend = []
block = []
for i in range(n):
    friend.append([])
    block.append([])
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friend[a].append(b)
    friend[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)

def cnt(p):
    q = queue.Queue()
    q.put(p)
    check = [False] * n
    check[p] = True
    ret = 0
    while not q.empty():
        s = q.get()
        for f in friend[s]:
            if check[f]: continue
            check[f] = True
            q.put(f)
            if f not in block[p]: ret += 1
    return ret

for i in range(n):
    print(cnt(i) - len(friend[i]), end = ' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
input = sys.stdin.readline

# int = int(input())
# s = input().split()
# i = list(map(int, input().split()))
# s = [input() for i in range(3)]

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

x = list(map(int, input().split()))
n = x[0]
m = x[1]
k = x[2]

uf = UnionFind(n)

frends = []
for i in range(n):
    frends.append([])

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

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

    uf.union(a, b)

c = [-1] * k
d = [-1] * k

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

    frends[c].append(d)
    frends[d].append(c)

ans = []
for i in range(n):
    ans.append(str(len(list(set(uf.members(i)) - set(frends[i]) - set([i])))))

print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, m, k = [int(v) for v in input().split()]
friends = defaultdict(set)
for _ in range(m):
    a, b = tuple(int(v) for v in input().split())
    friends[a].add(b)
    friends[b].add(a)
blocks = defaultdict(set)
for _ in range(k):
    c, d = tuple(int(v) for v in input().split())
    blocks[c].add(d)
    blocks[d].add(c)

fnets = []
unused = set(range(1, n + 1))
while len(unused) > 0:
    root = unused.pop()
    fnet = {root}
    que = deque(friends[root])
    while len(que) > 0:
        p = que.pop()
        if p in fnet:
            continue
        fnet.add(p)
        que.extend(friends[p])
    fnets.append(fnet)
    unused -= fnet

results = {}
for fnet in fnets:
    for p in fnet:
        results[p] = len(fnet - blocks[p] - friends[p]) - 1

print(" ".join(str(results[p]) for p in range(1, n + 1)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.ranks = [0] * 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.ranks[x] < self.ranks[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x]+=1

        # if self.parents[x] > self.parents[y]:
        #     x, y = y, x

        # self.parents[x] += self.parents[y]
        # self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def tup(a,b):
    return (min(a,b),max(a,b))

def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    friends = defaultdict(bool)
    group = UnionFind(N)
    for i in range(M):
        friends[tup(A[i]-1,B[i]-1)] = True
        group.union(A[i]-1,B[i]-1)
    for i in range(K):
        friends[tup(C[i]-1,D[i]-1)] = True
    result = ""
    isFirst = True
    roots = group.roots()
    rootSets = {r: set() for r in roots }
    for i in range(N):
        r = group.find(i)
        rootSets[r].add(i)
    for i in range(N):
        c = 0
        r = group.find(i)
        for g in rootSets[r]:
            if g != i and not friends[tup(i,g)]:
                c+= 1
        if not isFirst:
            result+=" "
        else:
            isFirst = False
        result+=str(c)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    C = [int()] * (K)  # type: "List[int]"
    D = [int()] * (K)  # type: "List[int]"
    for i in range(K):
        C[i] = int(next(tokens))
        D[i] = int(next(tokens))
    solve(N, M, K, A, B, C, D)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[C]>size[B]:
        P[B]=P[C]
    else:
        P[C]=P[B]
G=[0 for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    G[a]+=1
    G[b]+=1
    union(a,b)
#print(P)
PP=[]
for i in range(N+1):
    PP.append(find(P[i]))
#print(PP)
PPP=[0 for i in range(N+1)]
for i in range(1,N+1):
    PPP[PP[i]]+=1
#print(PPP)

B=[[]for i in range(N+1)]
for i in range(K):
    c,d=map(int,input().split())
    B[c].append(d)
    B[d].append(c)
#print(G)
#print(B)
ans=[]
for i in range(1,N+1):
    ANS=PPP[PP[i]]-1-G[i]
    for j in B[i]:
        if PP[j]==PP[i]:
            ANS-=1
    ans.append(ANS)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindWithRank(object):
    par = []
    rank = []
    cache = True
    log = []

    def __init__(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

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

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

    def unite(self, x, y):
        ox, oy = x, y
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            x, y = y, x
            self.par[y] = x
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if (self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return
            # 違う木に属していた場合rnkを見てくっつける方を決める
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if (self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

uf = UnionFind(n)
bd = dict()
fd = dict()

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    fd[200000 * a + b] = True
    fd[200000 * b + a] = True
    uf.Unite(a, b)
for i in range(k):
    c,d = map(int, input().split())
    c -= 1
    d -= 1
    bd[200000 * c + d] = True
    bd[200000 * d + c] = True

res = [0] * n
for i in range(n):
    for j in range(i+1, n):
        if (200000 * i + j) not in fd and (200000 * i + j) not in bd:
            if uf.isSameGroup(i, j):
                res[i] += 1
                res[j] += 1
print(" ".join(list(map(str, res))))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

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 and not i in self.block[x] and not i in self.friend[x]]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M, K = LI()
    uf = UnionFind(N)
    G = [[] for _ in range(N)]
    block = [set() for _ in range(N)]
    friend = [set() for _ in range(N)]

    for _ in range(M):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
        uf.union(a, b)
        friend[a].add(b)
        friend[b].add(a)

    for _ in range(K):
        a, b = LI_()
        block[a].add(b)
        block[b].add(a)
    uf.block = block
    uf.friend = friend
    for i in range(N):
        print(len(uf.members(i)) - 1, end=' ')
    print()
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m, k = map(int, input().split())
ab = [list(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
cd = [list(map(lambda x:int(x)-1, input().split())) for _ in range(k)]

adlist = [[] for i in range(n)]
neglist = [set() for i in range(n)]
for a, b in ab:
  adlist[a] += [b]
  adlist[b] += [a]
for c, d in cd:
  neglist[c].add(d)
  neglist[d].add(c)

dist = [0]*n 

def pro_bfs(v):
  q = deque([v])
  visited = [0]*n 
  visited[v] = 1 
  dist = [-1]*n 
  dist[v] = 0
  fri = []

  while q:
    u = q.popleft()
    for s in adlist[u]:
      if visited[s] == 0:
        visited[s] = 1
        q += [s]
        dist[s] = dist[u] + 1
        if dist[s] > 1:
          fri += [s]

  return set(fri)

def neg_bfs(v):
  q = deque([v])
  visited = [0]*n 
  visited[v] = 1 
  dist = [-1]*n 
  dist[v] = 0
  fri = []

  while q:
    u = q.popleft()
    for s in adlist[u]:
      if visited[s] == 0:
        visited[s] = 1
        q += [s]
        dist[s] = dist[u] + 1
        if dist[s] == 1:
          fri += [s]

  return fri

ans = []
for i in range(n):
  po = pro_bfs(i)
  ne = neglist[i]
  ans += [len(po-ne)]

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

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
graph = {i: set() for i in range(1, N + 1)}
banned = {i: set() for i in range(1, N + 1)}

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].add(B)
    graph[B].add(A)

for _ in range(K):
    C, D = map(int, input().split())
    banned[C].add(D)
    banned[D].add(C)


res = [0] * (N + 1)
for i in range(1, N + 1):
    queue = [i]
    seen = {i}
    while queue:
        new = []
        for cur in queue:
            if i != cur and cur not in graph[i] and cur not in banned[i]:
                res[i] += 1
            for nxt in graph[cur]:
                if nxt not in seen:
                    seen.add(nxt)
                    new.append(nxt)
        queue = new
print(*res[1:])

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
num = [1 for _ in range(n)]
pre = [i for i in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  num[a] += 1
  num[b] += 1
  A = [a]
  B = [b]
  la = 1
  lb = 1
  while a != pre[a]:
    a = pre[a]
    A.append(a)
    la += 1
  while b != pre[b]:
    b = pre[b]
    B.append(b)
    lb += 1
  #print(a,b)
  if a != b:
    if la < lb:
      pre[b] = a
      for aa in A:
        pre[aa] = a
      for bb in B:
        pre[bb] = a
    else:
      pre[a] = b
      for aa in B:
        pre[aa] = b
      for bb in B:
        pre[bb] = b
root = [10**6 for _ in range(n)]
cnt = [0 for _ in range(n)]
for i in range(n):
  if root[i] < 10**6:
    cnt[root[i]] += 1
    continue
  I = int(i)
  J = [I]
  while I != pre[I]:
    I = pre[I]
    J.append(I)
  for x in J:
    root[x] = I
  cnt[I] += 1
#print(pre)
#print(root)
#print(cnt)
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
#print(ans)
for _ in range(k):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  if root[a] == root[b]:
    ans[a] -= 1
    ans[b] -= 1
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        self.roots = [{i} for i in range(size)]
    def getRootID(self, i):
        r = self.roots[i]
        if isinstance(r, set):
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return len(self.getGroupSet(i))
    def getGroupSet(self, i):
        return self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] |= self.roots[r2]
        self.roots[r2] = r1
        return True

def main():
    N,M,K=mis()
    uf = UnionFindEx(N)
    frs = tuple(set() for _ in range(N))
    bls = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = mis()
        uf.connect(a-1, b-1)
        frs[a-1].add(b-1)
        frs[b-1].add(a-1)
    for _ in range(K):
        a, b = mis()
        bls[a-1].add(b-1)
        bls[b-1].add(a-1)
    for i in range(N):
        print(len(uf.getGroupSet(i) - frs[i] - bls[i]) - 1, end=' ')


main()

Submission status: Time Limit Exceeded

Solution code:
def inputs(): return (int(x) for x in 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 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 = inputs()
uf = UnionFind(N+1)
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)
    uf.union(x-1,y-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):
    for j in range(i+1,N):
        if j in f[i] or j in b[i]:
            continue
        if uf.same(i,j):
            ans[i]+=1
            ans[j]+=1
print(*ans)