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 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 set(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 main():
    N, M, K = map(int, input().split())
    friends = [set() for _ in range(N)]
    block = [set() for _ in range(N)]
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        friends[A].add(B)
        friends[B].add(A)
        uni.union(A,B)

    for _ in range(K):
        C, D = map(int, input().split())
        C -= 1
        D -= 1
        block[C].add(D)
        block[D].add(C)
    
    ans = [0] * N
    for i in range(N):
        ans[i] = len((uni.members(i) - friends[i]) - block[i]) - 1

    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import defaultdict
setrecursionlimit(100001)
n, m, k = map(int, input().split())
ab = []
cd = []
for _ in range(m):
    ab.append(list(map(int, input().split())))
for _ in range(k):
    cd.append(list(map(int, input().split())))
friendsof = defaultdict(list)
for a, b in ab:
    friendsof[a - 1].append(b - 1)
    friendsof[b - 1].append(a - 1)
enemiesof = defaultdict(list)
for c, d in cd:
    enemiesof[c - 1].append(d - 1)
    enemiesof[d - 1].append(c - 1)
canfrinums = []
def dps(i, output):
    output.append(i)
    for fr in friendsof[i]:
        if fr not in output:
            dps(fr, output)
for i in range(n):
    canfri_i = []
    dps(i, canfri_i)
    canfri_i = [x for x in canfri_i if x != i and x not in friendsof[i] and x not in enemiesof[i]]
    canfrinums.append(len(canfri_i))
print(' '.join(map(str, canfrinums)))

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


    
from collections import defaultdict

n, m, k = map(int, input().split())
uf = UnionFind(n+1)
friends = defaultdict(list)
block = defaultdict(list)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)
    friends[a].append(b)
    friends[b].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    block[c].append(d)
    block[d].append(c)


ans = []
for i in range(1, n+1):
    F = friends[i]
    M = uf.members(i)
    B = block[i]
    ans.append(len(set(M) - set(F) - set(B) - set([i])))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindVerSize():
  def __init__(self, N):
    self._parent = [n for n in range(0, N)]
    self._size = [1] * N
  def find_root(self, x):
    if self._parent[x] == x: 
      return x
    self._parent[x] = self.find_root(self._parent[x]) 
    return self._parent[x]
  def unite(self, x, y):
    gx = self.find_root(x)
    gy = self.find_root(y)
    if gx == gy:
      return
    if self._size[gx] < self._size[gy]:
      self._parent[gx] = gy
      self._size[gy] += self._size[gx]
    else:
      self._parent[gy] = gx
      self._size[gx] += self._size[gy]
  def is_same_group(self, x, y):
    return self.find_root(x) == self.find_root(y)
n,m,k = map(int,input().split())
f = [0 for _ in range(n+1)]
uf = UnionFindVerSize(n+1)
for i in range(m):
  ai,bi = map(int,input().split())
  uf.unite(ai,bi)
  f[ai] += 1
  f[bi] += 1
l = [[] for _ in range(n+1)]
for i in range(k):
  ci,di = map(int,input().split())
  l[ci].append(di)
  l[di].append(ci)
d = [-1 for i in range(n+1)]
for i in range(1,n+1):
  bf = 0
  for x in l[i]:
    if uf.is_same_group(i,x):
      bf += 1
  if d[i] != -1:
    print(d[i]-bf-f[i],end=" ")
    continue
  ff = []
  for j in range(i+1,n+1):
    if uf.is_same_group(i,j):
      ff.append(j)
  ll = len(ff)
  for y in ff:
    d[y] = ll
  print(ll-bf-f[i],end=" ")

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

u = UnionFind(n)

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

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

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

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

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

for y in u.all_group_members().values():
    x = set(y)
    for j in x:
        ans[j] = len(x - frends[j]) - 1


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

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n+1)
        self.rank = [0] * (n+1)

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

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

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

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

    def count(self, x):
        return -self.root[self.find(x)]


def main():
    n, m, k = map(int, input().split())
    sets1 = [set() for _ in range(n+1)]
    tree = UnionFind(n)
    for _ in range(m):
        a, b = (map(int, input().split()))
        tree.union(a, b)
        sets1[a].add(b)
        sets1[b].add(a)
    sets2 = [set() for _ in range(n+1)]
    for _ in range(k):
        c, d = (map(int, input().split()))
        sets2[c].add(d)
        sets2[d].add(c)

    ans = [0] * n
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                continue
            if j not in sets1[i] and j not in sets2[i] and tree.isSame(i, j):
                ans[i-1] += 1
    print(' '.join(map(str, ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]
        

from collections import defaultdict, Counter
count_friend = Counter()
friends = defaultdict(set)
blocks = defaultdict(set)
N, M, K = map(int, input().split())
ds = DisjointSet(N+1)
# graph = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    ds.unite(A, B)
    count_friend[A] += 1
    count_friend[B] += 1
for i in range(K):
    C, D = map(int, input().split())
    blocks[C].add(D)
    blocks[D].add(C)
c_ids = [ds.findSet(i) for i in range(N+1)]
for i in range(1, N+1):
    friends[c_ids[i]].add(i)
ans = []
for i in range(1, N+1):
    c_id = c_ids[i]
    ans += [len(friends[c_id]-blocks[i])-count_friend[i]-1]
print(' '.join(list(map(str, ans))))
# print(ds.p)

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

INF = 999999

n, m, k = map(int, input().split())
ab = [[INF]*n for _ in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	ab[a-1][b-1] = 1
	ab[b-1][a-1] = 1
for i in range(n):
	ab[i][i] = 0

cd = [[0]*n for _ in range(n)]
for _ in range(k):
	c, d = map(int, input().split())
	cd[c-1][d-1] = 1
	cd[d-1][c-1] = 1

ab = warshall_floyd(ab)

ans = ["" for _ in range(n)]
for i, abi in enumerate(ab):
	cnt = 0
	for j, abij in enumerate(abi):
		if cd[i][j] == 1:
			ab[i][j] = -1
		if ab[i][j] >= 2 and ab[i][j] != INF:
			cnt += 1
	ans[i] = str(cnt)

print(" ".join(ans))

Submission status: Time Limit Exceeded

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

class UnionFind(object):
    def __init__(self, N):
        # 初期状態を定義。ルートは -1から始まり、-X と負数でグループのサイズをもつ
        self.node = [-1] * N

    def root(self, x):
        if self.node[x] < 0:
            # それ自身がrootなら自分のポジションを返却
            return x
        else:
            # ルートを再帰で辿って、それぞれルートに直つなぎにする
            self.node[x] = self.root(self.node[x])
            # 自分がつながってるルートのポジションを返却
            return self.node[x]

    def size(self, x):
        # xが所属するグループのサイズを取得
        # サイズは負の数で管理されてるので、-1倍して返却
        return -self.node[self.root(x)]

    def connect(self, x, y):
        a = self.root(x)  # x のrootの位置
        b = self.root(y)  # y のrootの位置

        # もう同じグループなら何もしない
        if a == b:
            return

        # サイズが大きい方をaとして取り回す
        if self.size(a) < self.size(b):
            a, b = b, a

        # aのサイズをbのサイズを含む形に更新する（負数同士の足し算）
        self.node[a] += self.node[b]
        # bをaに連結する
        self.node[b] = a

        return

    def show_nodes(self):
        return self.node


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

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

    for _ in range(M):
        A, B = map(int,input().split())
        tree.connect(A-1, B-1)
        friends[A-1][B-1] = True
        friends[B-1][A-1] = True

    for _ in range(K):
        C, D = map(int,input().split())
        block[C-1][D-1] = True
        block[D-1][C-1] = True

    # per person
    ans = [0] * N
    for i in range(N):
        for j in range(i + 1, N):
            # already firend?
            # not blocK?
            if friends[i][j] or block[i][j]:
                continue

            if tree.root(i) == tree.root(j):
                ans[i] += 1
                ans[j] += 1

    print(*ans)


if __name__ == "__main__":
    main()

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

    if len(cluster_index[remain_index]) < len(cluster_index[delete_index]):
        remain_index, delete_index = delete_index, remain_index

    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)

    AB = []
    for _ in range(M):
        ab = tuple(map(int, input().split()))
        index = bisect.bisect_left(AB, ab)
        AB.insert(index, ab)

    for a, b in AB:
        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:
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)]

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:
# -*- coding: utf-8 -*-
N, M, K = map(int, input().split())

# 人iの友達関係リスト
set_Friend = [set() for i in range(N)]
for j in range(M):
  A, B = map(int, input().split())
  set_Friend[A-1].add(B-1)
  set_Friend[B-1].add(A-1)

# 人iのブロック関係リスト
set_Block = [set() for i in range(N)]
for j in range(K):
  C, D = map(int, input().split())
  set_Block[C-1].add(D-1)
  set_Block[D-1].add(C-1)

# 友達関係による連結成分
cluster_id = 0
clusters = []
clustering = [-1 for i in range(N)]
for i in range(N):
  if clustering[i]!=-1:
    continue
  cluster_prev = set([i])
  cluster_diff = set([i])
  while len(cluster_diff)>0:
    cluster_next = set()
    for j in cluster_diff:
      cluster_next = cluster_next | set_Friend[j]
    cluster_diff = cluster_next - cluster_prev
    cluster_prev = cluster_next | cluster_prev
  for k in cluster_prev:
    clustering[k] = cluster_id
  clusters.append(cluster_prev)
  cluster_id += 1

# 友達候補の人数を計算して出力
for i in range(N):
  id = clustering[i]
  cluster = clusters[id]
  print(len(cluster-set_Friend[i]-set_Block[i]-set([i])), end='')
  if i<=N:
    print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def answer():
    n, m, k = map(int, input().split())
    friend = defaultdict(set)
    block = defaultdict(set)
    group = defaultdict(set)
    cand = defaultdict(set)
    uft = defaultdict(int)
    for i in range(m):
        a, b = map(int, input().split())
        friend[a].add(b)
        friend[b].add(a)
    for j in range(k):
        c, d = map(int, input().split())
        block[c].add(d)
        block[d].add(c)
    for i in range(1, n+1):
        if uft[i] != 0:
            group[i] = group[uft[i]]
        else:
            group[i] = set()
            q = [i]
            while q:
                p = q.pop()
                if p in group[i]:
                    continue
                q += list(friend[p])
                group[i].add(p)
            for j in group[i]:
                uft[j] = i
        cand[i] = group[i] - friend[i] - block[i]
    return ' '.join(str(len(cand[i])-1) for i in range(1, n+1))

print(answer())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, M, K = map(int, input().split())
SNS = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  SNS[a][b] = 1
  SNS[b][a] = 1
for _ in range(K):
  a, b = map(int, input().split())
  SNS[a][b] = -1
  SNS[b][a] = -1
ans = [0]*(N+1)
i = 1
while i <= N:
  memo = [False]*(N+1)
  memo[i] = True
  q = deque()
  j = 1 
  while j <= N:
    if SNS[i][j] == 1:
      q.append(j)
    j += 1
  while q:
    f = q.pop()
    if memo[f]:
      continue
    memo[f] = True
    if SNS[i][f] == 0:
      ans[i] += 1
    j = 1
    while j <= N:
      if SNS[f][j] == 1:
        q.append(j)
      j += 1
  i += 1
s = "%d"%ans[1]
for a in ans[2:]:
  s += " %d"%a
print(s)

Submission status: Time Limit Exceeded

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

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]]
      
uf=UnionFind(N)
for i in range(N):
  for j in AB[i]:
    uf.union(i,j-1)

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

Submission status: Time Limit Exceeded

Solution code:
class UnionFindByRank():
  def __init__(self, n):
    self.parents = list(range(n))
    self.rank = [0] * n

  def find(self, x):
    if self.parents[x] == x:
      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.rank[x] < self.rank[y]:
      self.parents[x] = y
    else:
      self.parents[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1

if __name__ == '__main__':
  N, M, K = list(map(int, input().split()))
  uf = UnionFindByRank(N + 1)
  #A, B, C, D = [0] * M, [0] * M, [0] * K, [0] * K
  friends = set()
  blocks = set()
  for i in range(M):
    # friends
    #A[i], B[i] = list(map(int, input().split()))
    pair = tuple(sorted(map(int, input().split())))
    friends.add(pair)
    uf.union(pair[0], pair[1])
  for i in range(K):
    # blocks
    blocks.add(tuple(sorted(map(int, input().split()))))

res = []

for i in range(1, N + 1):
  cnt = 0
  for j in range(1, N + 1):
    if i != j and uf.find(i) == uf.find(j) and \
        not tuple(sorted([i, j])) in blocks and \
        not tuple(sorted([i, j])) in friends:
      cnt += 1
  res.append(cnt)

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

Submission status: Time Limit Exceeded

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

n,m,k = map(int, input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
cd = [list(map(int,input().split())) for _ in range(k)]

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

uf = UnionFind(n+1)
for a,b in ab:
    uf.union(a,b)


f_dict = {}
b_dict = {}
for i in range(1,n+1):
    f_dict[i] = []
    b_dict[i] = []

for a,b in ab:
    f_dict[a].append(b)
    f_dict[b].append(a)

for c,d in cd:
    b_dict[c].append(d)
    b_dict[d].append(c)

ans = [0] * (n+1)

for i in range(1,n+1):
    group = uf.members(i)
    for j in b_dict[i]:
        group.discard(j)
    ans[i] = len(group) - len(f_dict[i]) - 1

print(' '.join(map(str, ans[1:])))

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 = [0] * N
    for _ in range(M):
        a, b = map(int, input().split())
        U.union(a - 1, b - 1)
        FR[a - 1] += 1
        FR[b - 1] += 1
    BL = [set() for _ in range(N)]
    for _ in range(K):
        c, d = map(int, input().split())
        BL[c - 1].add(d - 1)
        BL[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)] - BL[i]) - 1 - FR[i]) for i in range(N)))

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friend = [0] * (n+1)
block = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    friend[a] += 1
    friend[b] += 1
    uf.union(a-1, b-1)
for _ in range(k):
    c, d = map(int, input().split())
    if uf.same(c-1, d-1):
        block[c] += 1
        block[d] += 1

groups = list(uf.all_group_members().values())
w = [0] * (n+1)

for group in groups:
    for member in group:
        member += 1
        w[member] = len(group) - friend[member] - block[member] - 1

print(*w[1:])