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 defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def resolve():
    n, m, k = map(int, input().split())
    u = UnionFind(n)
    d = defaultdict(lambda: [])
    e = defaultdict(lambda: [])
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        u.union(a, b)
        d[a].append(b)
        d[b].append(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        e[a].append(b)
        e[b].append(a)
    ans = [0] * n
    for i in range(n):
        l = u.members(i)
        for j in l:
            if j != i and (not j in d[i]) and (not j in e[i]):
                ans[i] += 1
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
CD=[[] for _ in range(N)]
for _ in range(K):
  c,d=map(int,input().split())
  CD[c-1].append(d)
  CD[d-1].append(c)

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 i+1 not in CD[x] and [i+1,x+1] not in AB and [x+1,i+1] not in AB]
      
uf=UnionFind(N)
for i in range(M):
  uf.union(AB[i][0]-1,AB[i][1]-1)

ans=[0]*N
for i in range(N):
  ans[i]=len(uf.members(i))-1 
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(500000)

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parent = [0] * (n+3)
        self.num = [1] * (n+3)
        self.diff_weight = [0] * (n+3)
        for i in range(n):
            self.parent[i] = i
    
    def root(self, x):
        if x == self.parent[x]:
            return x
        else:
            r = self.root(self.parent[x])
            self.diff_weight[r] += self.diff_weight[self.parent[x]]
            self.parent[x] = r
            return r
    
    def unite(self, a, b, w = 0):
        w += self.weight(a) - self.weight(b)
        a = self.root(a)
        b = self.root(b)
        if a == b:
            return
        self.parent[b] = a
        sum_v = self.num[a] + self.num[b]
        self.num[a] = sum_v
        self.num[b] = sum_v
        self.diff_weight[b] = w
        
    def same(self, a, b):
        return (self.root(a) == self.root(b))
    
    def sz(self, x):
        return self.num[self.root(x)]
    
    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]

    def diff(self, a, b):
        return self.weight(b) - self.weight(a)


if __name__ == "__main__":

    N,M,K = map(int, readline().split())
    A = [0] * (M+5)
    B = [0] * (M+5)
    C = [0] * (K+5)
    D = [0] * (K+5)
    for i in range(M):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        A[i] = a 
        B[i] = b 
    for i in range(K):
        a,b = map(int, readline().split())
        a -= 1
        b -= 1
        C[i] = a 
        D[i] = b 
    uf = UnionFind(100010)
    for i in range(M):
        uf.unite(A[i], B[i])

    arr = [[] for _ in range(N+2)]
    edge = [[] for _ in range(N+2)]
    for i in range(N):
        arr[uf.root(i)].append(i)
    
    for i in range(M):
        if uf.same(A[i], B[i]):
            edge[uf.root(A[i])].append(i)
    
    for i in range(K):
        if uf.same(C[i], D[i]):
            edge[uf.root(C[i])].append(i + M)
        

    ans = ["0"] * N
    for i in range(N):
        dd = {}
        if len(arr[i]) == 0:
            continue
        sz = uf.sz(i)
        for j, v in enumerate(arr[i]):
            dd[v] = j
        friends = [0] * (sz+2)
        for e in edge[i]:
            if e <= M-1:
                friends[dd[A[e]]] += 1
                friends[dd[B[e]]] += 1
            else:
                friends[dd[C[e-M]]] += 1
                friends[dd[D[e-M]]] += 1
        for v in arr[i]:
            res = sz - friends[dd[v]] - 1
            ans[v] = str(res)
    print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M, K = map(int, input().split())

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

for k in range(K):
    c, d = map(int, input().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)

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=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
import bisect
from math import factorial

def update_cluster(cluster, cluster_index, a, b):
    remain_index = cluster[a]
    delete_index = cluster[b]
    if remain_index == delete_index:
        return
    movers = cluster_index[delete_index]
    for mover in movers:
        cluster[mover] = remain_index
        cluster_index[remain_index].add(mover)

    del cluster_index[delete_index]

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

    cluster = {i+1: i+1 for i in range(N)}
    cluster_index = {i+1: set([i+1]) for i in range(N)}
    blocks = defaultdict(set)

    for _ in range(M):
        a, b = map(int, input().split())
        update_cluster(cluster, cluster_index, a, b)
        blocks[a].add(b)
        blocks[b].add(a)

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

    friends = []
    for p, index in cluster.items():
        candidates = cluster_index[index]
        num = len(candidates - blocks[p]) - 1
        friends.append(str(num))

    print(" ".join(friends))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

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

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

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

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


N, M, K = map(int, input().split())
uf = UnionFind(N+1)

friend = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    friend[a].append(b)
    friend[b].append(a)
    uf.union(a, b)


block = defaultdict(list)
for _ in range(K):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

for i in range(1, N+1):
    ans = uf.size(i)-1
    for f in friend[i]:
        if uf.same(i, f):
            ans -= 1
    for b in block[i]:
        if uf.same(i, b):
            ans -= 1
    print(ans, end=" ")

print("")

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m, k = map(int,input().split())
a = [[] for i in range(n)]
for i in range(m):
  x, y = map(int,input().split())
  a[x-1].append(y-1)
  a[y-1].append(x-1)
c = [[] for i in range(n)]
for i in range(k):
  x, y = map(int,input().split())
  c[x-1].append(y-1)
  c[y-1].append(x-1)
f = []
for i in range(n):
  x = []
  y = copy.deepcopy(a[i])
  z = a[i]+[i]
  while y:
    u = y.pop()
    for v in a[u]:
      if not(v in x+a[i]+c[i]+[i]):
        x.append(v)
      if not(v in z):
        y.append(v)
        z.append(v)
  f.append(str(len(x)))
print(" ".join(f))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
N,M,K= map(int,input().split())

friend = defaultdict(list)
#block = defaultdict(list)

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

IDs = [-1] * (N+1)
ID = 0
for i in range(1,N+1):
    if IDs[i] != -1:
        continue
    dq = deque([i])
    while dq:
        v = dq.popleft()
        IDs[v] = ID
        for nv in friend[v]:
            if IDs[nv] == -1:
                dq.append(nv)
    ID += 1

group = Counter(IDs)

ans = []
for i in range(1,N+1):
    temp = group[IDs[i]] - len(friend[i]) - 1
    ans.append(temp)

for c,d in block:
    if IDs[c] == IDs[d]:
        ans[c-1] -= 1
        ans[d-1] -= 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]
def main():
    N, M, K = map(int, input().split())
    fd = defaultdict(list)
    uf = UnionFind(N+1)
    for _ in range(M):
        a, b = map(int, input().split())
        if a in fd:
            fd[a].append(b)
        else:
            fd[a] = [b]
        if b in fd:
            fd[b].append(a)
        else:
            fd[b] = [a]
        uf.union(a,b)
    for _ in range(K):
        c, d = map(int, input().split())
        if uf.same(c, d):
            fd[c].append(d)
            fd[d].append(c)
    r = []
    for i in range(1, N+1):
        r.append(len(uf.members(i))-len(fd[i])-1)
    print(' '.join(str(i) for i in r))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M, K = map(int, input().split())
repn = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    repn[a].append(b)
    repn[b].append(a)

block = [[] for _ in range(N + 1)]
for _ in range(K):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)

def cand(i):
    visited = [0] * (N + 1)
    visited[i] = 1
    q = deque([i])
    while q:
        u = q.popleft()
        for v in repn[u]:
            if visited[v] == 0:
                visited[v] = 1
                q.append(v)
    
    for j in block[i]:
        visited[j] = 0
    
    for j in repn[i]:
        visited[j] = 0
    
    return sum(visited)

ans = []
for i in range(1, N + 1):
    ans.append(cand(i) - 1)
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
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 = [[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

friend = warshall_floyd(friend)

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

ans = [0 for i in range(n)]

for i in range(n):
  for j in range(n):
    if i != j and 1 < friend[i][j] < 10 ** 10:
      ans[i] += 1

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

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 for _ in range(n)] for _ in range(n)]

ans=[n-1]*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):
    tmp=tk.members(i)
    ans=-1
    for val in tmp:
        if not kk[i][val]:
            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]

uf = UnionFind(N)

friend = [[False]*N for _ in range(N)]

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

block = [[False]*N for _ in range(N)]

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

res = []
for i in range(N):
    g = uf.members(i)
    cnt = -1
    for x in g:
        if friend[i][x] or block[i][x]:
            continue
        cnt += 1
    res.append(str(cnt))

print(" ".join(res))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        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 main():
    N, M, K = list(map(int, input().split()))
    U = UnionFind(N)
    FR = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1].add(b - 1)
        FR[b - 1].add(a - 1)
    #BL = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        FR[c - 1].add(d - 1)
        FR[d - 1].add(c - 1)
    LS = {}
    for i in range(N):
        t = U.find(i)
        if t not in LS:
            LS[t] = set()
        LS[t].add(i)

    print(' '.join(str(len(LS[U.find(i)] - FR[i]) - 1) for i in range(N)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]    
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
def same(x,y):
    return find(x) == find(y)

def main():
    n,m,k = inpm()
    global par,rank
    par = [i for i in range(n)]
    rank = [0 for _ in range(n)]
    ok = defaultdict(int)
    block = defaultdict(int)
    for _ in range(m):
        a,b = inpm()
        unite(a-1,b-1)
        key = ' '.join([str(a-1),str(b-1)])
        ok[key] = 1
        key = ' '.join([str(b-1),str(a-1)])
        ok[key] = 1
    for _ in range(k):
        c,d = inpm()
        key = ' '.join([str(c-1),str(d-1)])
        block[key] = 1
        key = ' '.join([str(d-1),str(c-1)])
        block[key] = 1
    ans = [0 for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            if block[' '.join([str(i),str(j)])]:
                continue
            if ok[' '.join([str(i),str(j)])]:
                continue
            if same(i,j):
                ans[i] += 1
                ans[j] += 1
    print(*ans)

    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

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


def main():
    N, M, K = [int(x) for x in input().split()]
    friblo = [set() for j in range(N)]

    u = UnionFind(N)
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        friblo[a - 1].add(b - 1)
        friblo[b - 1].add(a - 1)
        u.union(a - 1, b - 1)

    for _ in range(K):
        a, b = [int(x) for x in input().split()]
        friblo[a - 1].add(b - 1)
        friblo[b - 1].add(a - 1)

    for i in range(N):
        friblo[i].add(i)
        print(len(set(u.members(i)) - friblo[i]), end=" ")


if __name__ == '__main__':
    main()

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 = []
  B = []
  while a != pre[a]:
    a = pre[a]
    A.append(a)
  while b != pre[b]:
    b = pre[b]
    B.append(b)
  if a != b:
    pre[b] = a
    for aa in A:
      pre[aa] = a
    for bb in B:
      pre[bb] = a
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
ans = []
for i in range(n):
  ans.append(cnt[root[i]]-num[i])
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:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.tree = {i: i for i in xrange(n)}
    
    def root(self, n):
        if self.tree[n] == n:
            return n
        return self.root(self.tree[n])

    def merge(self, a, b):
        aa = self.root(a)
        bb = self.root(b)
        self.tree[aa] = bb

    def clusters(self):
        c = {}
        for i in xrange(self.n):
            j = self.root(i)
            c.setdefault(j, set()).add(i)
        return c.values()


def main():
    n, m, k = map(int, raw_input().split())
    uf = UnionFind(n)
    ff = {}
    block = {}
    for _ in xrange(m):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        ff.setdefault(a, set()).add(b)
        ff.setdefault(b, set()).add(a)
        uf.merge(a, b)
    for _ in xrange(k):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        block.setdefault(a, set()).add(b)
        block.setdefault(b, set()).add(a)

    clusters = uf.clusters()
    ans = [0] * n
    for cluster in clusters:
        for i in cluster:
            size = len(cluster - {i} - block.get(i, set()) - ff.get(i, set()))
            ans[i] = size
    print ' '.join(map(str, ans))

main()

Submission status: Time Limit Exceeded

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

N, M, K = map(int, input().split())
friend_1 = []
friend_2 = []
n_friends = [0]*N
for i in range(M):
    new1, new2 = map(int, input().split())
    friend_1.append(new1 - 1)
    friend_2.append(new2 - 1)
    n_friends[new1-1] += 1
    n_friends[new2-1] += 1
    
block_1 = []
block_2 = []
n_blocks = [0]*N
for i in range(K):
    new1, new2 = map(int, input().split())
    block_1.append(new1 - 1)
    block_2.append(new2 - 1)
    n_blocks[new1-1] += 1
    n_blocks[new2-1] += 1
    
csr = csr_matrix(([1]*M, (friend_1, friend_2)), (N, N))
n_components, labels = connected_components(csr)

ans = [0]*N
count = [0]*n_components
for i in range(n_components):
    count[i] = np.count_nonzero(labels==i)

for i in range(N):
    ans[i] = count[labels[i]] - 1
    ans[i] -= n_friends[i]

for i in range(K):
    a = block_1[i]
    b = block_2[i]
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

print(*ans)

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

def main():
	N,M,K=map(int,input().split())
	#S=input().rstrip()
	#N=int(input())
	#vA=list(map(int,input().split()))
	vAB=[tuple(map(int,input().split()))
		 for _ in [0,]*M]
	vCD=[tuple(map(int,input().split()))
		 for _ in [0,]*K]
	
	uf = UnionFind(N)
	vF = [set() for _ in [0,]*N] # friend
	vB = [set() for _ in [0,]*N] # block
	
	for a,b in vAB:
		uf.union(a-1,b-1)
		vF[a-1] |= {b-1}
		vF[b-1] |= {a-1}
	
	for c,d in vCD:
		vB[c-1] |= {d-1}
		vB[d-1] |= {c-1}
	
	#vR = [uf.size(i)-1-vF[i]-vB[i]
	#      for i in range(N)]
	
	vR = []
	for i in range(N):
		g = uf.size(i)
		gm = uf.members(i)
		f = sum(gmm in vF[i] for gmm in gm)
		b = sum(gmm in vB[i] for gmm in gm)
		vR.append(g - 1 - f - b)
		
	print(*vR)
	
main()