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 scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

from collections import Counter

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

g = [[0] * n for _ in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    g[a][b] = 1
    g[b][a] = 1

csr = csr_matrix(g)
comp, labels = connected_components(csr)

counter = Counter(labels)

ans = [counter[labels[i]] - 1 for i in range(n)]

for a, b in ab:
    a -= 1
    b -= 1
    if labels[a] == labels[b]:
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    c -= 1
    d -= 1
    if labels[c] == labels[d]:
        ans[c] -= 1
        ans[d] -= 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())

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
        self.sets = [set([i]) for i in range(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
        self.sets[x] |= self.sets[y]

    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)
    print(' '.join(str(len(U.sets[U.find(i)] - FR[i]) - 1) for i in range(N)))

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


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 d[i]:
            l.remove(j)
        for j in e[i]:
            if j in l:
                l.remove(j)
        ans[i] = len(l) - 1
    print(*ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

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

block_edges = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    block_edges[c].add(d)
    block_edges[d].add(c)

visited = [False] * N
cnt = 0

def dfs(u, s):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        if v == s:
            continue

        if v not in block_edges[s] and v not in edges[s]:
            global  cnt
            cnt += 1

        dfs(v, s)


ans = []
for i in range(N):
    visited = [False] * N
    cnt = 0
    for v in edges[i]:
        dfs(v, i)
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


n, m, k = map(int,input().split())
friends=[0]*n
uf = UnionFind(n)
for i in range(m):
    a, b = map(int,input().split())
    uf.union(a-1, b-1)
    friends[a-1]+=1
    friends[b-1]+=1

nowlist=list(uf.all_group_members().values())

koho=[0]*n
group=[0]*n
number=1
for nl in nowlist:
    ng=len(nl)
    for nnl in nl:
        koho[nnl]=ng
        group[nnl]=number
    number+=1

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

for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N,M,K=map(int,input().split())
FB=[[False for i in range(N+1)] for j in range(N+1)]

par = [i for i in range(N+1)]
rank = [0 for i in range(N+1)]
 
def find(x):
    if x==par[x]:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
 
 
def unite(x,y):
    rx=find(x)
    ry=find(y)

    if rx==ry:
        return
    
    
    if rank[rx]<rank[ry]:
        par[rx]=ry
    else:
        par[ry]=rx

    if rank[rx]==rank[ry]:
        rank[rx]+=1
 

def some(x,y):
    return find(x)==find(y)
 
for i in range(M):
    A,B=map(int,input().split())
    unite(A,B)
    FB[A][B]=True
    FB[B][A]=True

for i in range(K):
    C,D=map(int,input().split())
    FB[C][D]=True
    FB[D][C]=True

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

for i in range(1,N+1):
    for j in range(1,N+1):
        if FB[i][j]:
            continue
        else:
            if some(i,j) and i!=j:
                ans[i-1]+=1


print(*ans)

Submission status: Time Limit Exceeded

Solution code:
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)]

friends = {i:set() for i in range(1, N+1)}

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

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

from collections import deque
areas = {i:set() for i in range(1, N+1)}
for i in range(1, N+1):
    q = deque([i])
    while q:
        p = q.pop()
        for f in friends[p]:
            if f not in areas[i] and f != i:
                q.appendleft(f)
                areas[i].add(f)

ans = []
for i in range(1, N+1):
    ans.append(len(areas[i] - friends[i] - blocks[i]))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    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()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
	N, M, K = MAP()
	friends = defaultdict(list)
	tree = UnionFind(N)
	for _ in range(M):
		A, B = MAP()
		tree.union(A-1, B-1)
		friends[A-1].append(B-1)
		friends[B-1].append(A-1)

	blocks = defaultdict(list)
	for _ in range(K):
		C, D = MAP()
		blocks[C-1].append(D-1)
		blocks[D-1].append(C-1)

	for i in range(N):
		minus = 0
		for b in blocks[i]:
			if b in tree.members(i):
				minus += 1
		print(tree.size(i)-len(friends[i])-1-minus, end=" ")
	print()
	
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

visited = [False] * N
cnt = 0

def dfs(u, s):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        if v == s:
            continue

        if v not in block_edges[s] and v not in edges[s]:
            global  cnt
            cnt += 1

        dfs(v, s)


ans = []
for i in range(N):
    visited = [False] * N
    cnt = 0
    for v in edges[i]:
        dfs(v, i)
    ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,k=map(int,input().split())
friend={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  friend[a-1].add(b-1)
  friend[b-1].add(a-1)
block={i:set() for i in range(n)}
for i in range(k):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)
checked=set()
belongs=[-1 for i in range(n)]
renketsu=[]
b = 0
for i in range(n):
  if i in checked:
    continue
  g = set()
  queue = deque([i])
  while(queue):
    t = queue.popleft()
    if t in checked:
      continue
    checked.add(t)
    g.add(t)
    belongs[t] = b
    queue.extend(friend[t])
  renketsu.append(g)
  b += 1
fnum=[]
for i in range(n):
  fnum.append(len( renketsu[belongs[i]] - friend[i] - block[i])-1)
print(' '.join(map(str,fnum)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n, m, k = map(int, input().split())
f = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for _ in range(m):
    a, _b = map(int, input().split())
    f[a-1].append(_b-1)
    f[_b-1].append(a-1)
for _ in range(k):
    a, _b = map(int, input().split())
    b[a-1].append(_b-1)
    b[_b-1].append(a-1)

for i in range(n):
    ans = 0
    checked = [False]*n
    checked[i] = True
    def search(node):
        global ans, checked
        if node != i and node not in f[i] and node not in b[i]:
            ans += 1
        for _node in f[node]:
            if not checked[_node]:
                checked[_node] = True
                search(_node)
        return
    search(i)
    print(ans, end=" " if i != n-1 else "\n")

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,m,k = get_nums_l()

lines = list(map(lambda s: s.strip(), sys.stdin.readlines()))
friends = list(map(lambda s: list(map(int, s.split())), lines[:m]))
blocks = list(map(lambda s: list(map(int, s.split())), lines[m:]))

# Union-Find
def root(i):
    if node_groups[i] == i:
        return i
    else:
        node_groups[i] = root(node_groups[i])
        return node_groups[i]

def same(a, b):
    return root(a) == root(b)

def size(i):
    return group_sizes[root(i)]

def unite(a, b):
    a = root(a)
    b = root(b)

    if a == b:
        return

    if group_ranks[a] < group_ranks[b]:
        group_sizes[b] += size(a)
        node_groups[a] = b
    else:
        group_sizes[a] += size(b)
        node_groups[b] = a
        if group_ranks[a] == group_ranks[b]:
            group_ranks[a] += 1

nodes = n+1
node_groups = [ i for i in range(nodes)]
group_sizes = [ 1 for _ in range(nodes)]
group_ranks = [ 0 for _ in range(nodes)]

edges = []
for f in friends:
    unite(f[0], f[1])

group_nodes = [set() for _ in range(nodes)]
for node in range(1, n+1):
    group_nodes[root(node)].add(node)

blocked_by = [ set() for _ in range(nodes)]
for bl in blocks:
    blocked_by[bl[0]].add(bl[1])
    blocked_by[bl[1]].add(bl[0])

# log("BLOCK", blocked_by)

followed_by = [ set() for _ in range(nodes)]
for fr in friends:
    followed_by[fr[0]].add(fr[1])
    followed_by[fr[1]].add(fr[0])
# log("FIRIENDS", friends)
# log("FOLLOW", followed_by)

for node in range(nodes):
    blocked_by[node].add(node)

ans = []
for node in range(1, n+1):
    kouho = (group_nodes[root(node)] - followed_by[node]) - blocked_by[node]
    ans.append(len(kouho))

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
edges1 = [[] for _ in range(N + 1)]
edges2 = [[] for _ in range(N + 1)]


A, B = [], []
C, D = [], []
for _ in range(M):
    _a, _b = list(map(int, input().split()))
    A.append(_a)
    B.append(_b)
    edges1[_a].append(_b)
    edges1[_b].append(_a)

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    C.append(_c)
    D.append(_d)
    edges2[_c].append(_d)
    edges2[_d].append(_c)

# print(edges1)
# print(edges2)

def dfs(v):
    visited = [False for _ in range(N + 1)]
    queue = []
    heappush(queue, v)
    visited[v] = True

    counter = 0

    while queue:
        n = heappop(queue)
        for u in edges1[n]:
            if not visited[u]:
                visited[u] = True
                if u not in edges1[v] and u not in edges2[v]:
                    counter += 1
                heappush(queue, u)
    return counter


# all search
ans = []
for v in range(1, N + 1):
    counter = dfs(v)
    ans.append(counter)
print(" ".join(map(str, ans)))

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

    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 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)
    blocks = 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):
        blocks[tup(C[i]-1,D[i]-1)] = True
    result = ""
    isFirst = True
    for i in range(N):
        c = 0
        for v in group.members(i):
            if i != v and not friends[tup(i,v)] and not blocks[tup(i,v)]:
                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(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 = []
    u = UnionFind(N)
    for i in range(N):
        friblo.append(set())

    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:
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)
d = [0 for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a,b)
    d[a] -= 1
    d[b] -= 1
for i in range(1,N+1):
    n = len(uf.members(i))
    d[i] += n - 1
for j in range(K):
    a,b = map(int,input().split())
    if uf.same(a,b):
        d[a] -= 1
        d[b] -= 1
d.pop(0)
for i in range(N):
    d[i] = str(d[i])
d = ' '.join(d)
print(d)

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 = []
cnt = [0 for _ in range(n)]
for i in range(n):
  I = int(i)
  while I != pre[I]:
    I = pre[I]
  root.append(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:
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())
friends=[0]*n
uf = UnionFind(n)
for i in range(m):
    a, b = map(int,input().split())
    uf.union(a-1, b-1)
    friends[a-1]+=1
    friends[b-1]+=1

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

nowlist=list(uf.all_group_members().values())
#print(friends)

koho=[0]*n
for nl in nowlist:
    ng=len(nl)
    for nnl in nl:
        koho[nnl]=ng

#print(koho)
for i in range(k):
    c, d = map(int,input().split())
    if uf.same(c-1, d-1):
        koho[c-1]-=1
        koho[d-1]-=1

#print(koho)
#print(friends)
for i in range(n):
    print(koho[i]-friends[i]-1, end=" ")

Submission status: Time Limit Exceeded

Solution code:
N,M,K = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]
CD = [list(map(int,input().split())) for _ in [0]*K]

import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self,N):
        self.Parent = list(range(N))
    def get_Parent(self,n):
        if self.Parent[n] == n:return n
        p = self.get_Parent(self.Parent[n])
        self.Parent[n] = p
        return p
    def merge(self,x,y):
        x = self.get_Parent(x)
        y = self.get_Parent(y)
        if x!=y: self.Parent[y] = x
        return
    def is_united(self,x,y):
        return self.get_Parent(x)==self.get_Parent(y)

U = UnionFind(N)
E_f = [[] for _ in [0]*N]
for a,b in AB:
    a -= 1
    b -= 1
    U.merge(a,b)
    E_f[a].append(b)
    E_f[b].append(a)
group = [set() for _ in [0]*N]
for i in range(N):
    p = U.get_Parent(i)
    group[p].add(i)

E_b = [[] for _ in [0]*N]
for c,d in CD:
    c -= 1
    d -= 1
    E_b[c].append(d)
    E_b[d].append(c)

ans = [0]*N
for i in range(N):
    p = U.get_Parent(i)
    tmp = group[p].copy()
    for b in E_b[i]:
        if b in tmp:tmp.remove(b)
    ans[i] = len(tmp) - len(E_f[i]) - 1

print(*ans)