Problem:


Score : 400 points

Problem Statement

An SNS has N users - User 1, User 2, \cdots, User N.

Between these N users, there are some relationships - M friendships and K blockships.

For each i = 1, 2, \cdots, M, there is a bidirectional friendship between User A_i and User B_i.

For each i = 1, 2, \cdots, K, there is a bidirectional blockship between User C_i and User D_i.

We define User a to be a friend candidate for User b when all of the following four conditions are satisfied:

a \neq b.

There is not a friendship between User a and User b.

There is not a blockship between User a and User b.

There exists a sequence c_0, c_1, c_2, \cdots, c_L consisting of integers between 1 and N (inclusive) such that c_0 = a, c_L = b, and there is a friendship between User c_i and c_{i+1} for each i = 0, 1, \cdots, L - 1.

For each user i = 1, 2, ... N, how many friend candidates does it have?

Constraints

All values in input are integers.

2 ≤ N ≤ 10^5

0 \leq M \leq 10^5

0 \leq K \leq 10^5

1 \leq A_i, B_i \leq N

A_i \neq B_i

1 \leq C_i, D_i \leq N

C_i \neq D_i

(A_i, B_i) \neq (A_j, B_j) (i \neq j)

(A_i, B_i) \neq (B_j, A_j)

(C_i, D_i) \neq (C_j, D_j) (i \neq j)

(C_i, D_i) \neq (D_j, C_j)

(A_i, B_i) \neq (C_j, D_j)

(A_i, B_i) \neq (D_j, C_j)

Input

Input is given from Standard Input in the following format:

N M K
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_K D_K

Output

Print the answers in order, with space in between.

Sample Input 1

4 4 1
2 1
1 3
3 2
3 4
4 1

Sample Output 1

0 1 0 1

There is a friendship between User 2 and 3, and between 3 and 4. Also, there is no friendship or blockship between User 2 and 4. Thus, User 4 is a friend candidate for User 2.

However, neither User 1 or 3 is a friend candidate for User 2, so User 2 has one friend candidate.

Sample Input 2

5 10 0
1 2
1 3
1 4
1 5
3 2
2 4
2 5
4 3
5 3
4 5

Sample Output 2

0 0 0 0 0

Everyone is a friend of everyone else and has no friend candidate.

Sample Input 3

10 9 3
10 1
6 7
8 2
2 5
8 4
7 3
10 9
6 4
5 8
2 6
7 5
3 1

Sample Output 3

1 3 5 4 3 3 3 3 1 0



Sample input:
4 4 1
2 1
1 3
3 2
3 4
4 1


Sample output:
0 1 0 1

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)
from sys import stdin 
input=stdin.readline
friend=[set() for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
friends=[set() for i in range(n)]
for i in range(n):
    friends[find(i)].add(i)

print(*[len(friends[find(i)]-(anti[i]|friend[i]|{i})) for i in range(n)],sep=" ")

Submission status: Time Limit Exceeded

Solution code:
inputs = open(0).readlines()
n, m, k = map(int, inputs[0].split())
AB = [tuple(map(int, ab.split())) for ab in inputs[1:m+1]]
CD = [tuple(map(int, cd.split())) for cd in inputs[m+1:]]

def dfs(root, graph):
        nodes, stack = [], [root]
        while stack:
            current_node = stack.pop()
            if current_node in nodes:
                continue
            nodes.append(current_node)
            for n in graph[current_node]:
                if n not in nodes:
                    stack.append(n)
        return nodes

friends = [set() for _ in range(n)]
for n0, n1 in AB:
    friends[n0-1].add(n1-1)
    friends[n1-1].add(n0-1)
blocks = [set() for _ in range(n)]
for n0, n1 in CD:
    blocks[n0-1].add(n1-1)
    blocks[n1-1].add(n0-1)

connected_nodes = {}
candidates = []
for i in range(n):
    if i not in connected_nodes:
        nodes = set(dfs(i, friends))
        for j in nodes:
            connected_nodes[j] = nodes
    else:
        nodes = connected_nodes[i]
    candidates.append(len(nodes) - len(friends[i]) - len(nodes & blocks[i]) - 1)
print(*candidates)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
par=[i for i in range(n)]
rank=[0 for i in range(n)]
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    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_par(x)==find_par(y)
friend=[set() for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
G=[find_par(i)  for i in range(n)]
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
friends=[set() for i in range(n)]
for i in range(n):
    friends[par[i]].add(i)
psfriend=[friends[par[i]] for i in range(n)]

print(*[len(psfriend[i]-anti[i]-friend[i]-set([i])) for i in range(n)],sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,k,m=map(int,input().split())

F=[[] for _ in range(n)]
B=[[] for _ in range(n)]

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

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


def find(i):
    dis=0
    Q=deque([[i,dis]])
    ans=0
    visited={i}
    while Q:
        f,dis=Q.pop()
        if dis>1 and not f in B[i]:
            ans+=1

        for j in F[f]:
            if j in visited:
                continue
            Q.appendleft([j,dis+1])
            visited.add(j)
    return ans

ANS=[]
for i in range(n):
    ANS.append(find(i))
print(*ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

N,M,K=LI()
UF=UnionFindTree(N)
NUMF = [0]*(N+1)
for i in range(M):
    f,t = LI()
    UF.unite(f,t)
    NUMF[f] += 1
    NUMF[t] += 1

BLL=[]
for j in range(K):
    f, t = LI()
    BLL.append((f,t))
    BLL.append((t,f))
BLL.sort()
GPS = [0]*(N+1)

for i in range(1, N+1):
    UF.find(i)
    GPS[UF.nodes[i]] += 1

ptr = 0
K2 = 2*K
for i in range(1, N+1):
    res = GPS[UF.find(i)] - 1 - NUMF[i]
    while BLL and ptr < K2 and i == BLL[ptr][0]:
        res -= UF.is_same(BLL[ptr][0], BLL[ptr][1])
        ptr += 1
    print(res, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# # import heapq
# # from copy import deepcopy
from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math

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

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

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

def suggest(s):
    count = 0
    seen = [False] * n
    que = deque([s])
    while que:
        start = que.popleft()
        seen[start] = True
        for i in friend[start]:
            if seen[i]: continue
            else:
                que.append(i)

    for i in range(n):
        if i != s and seen[i] and (i not in friend[s]) and (i not in block[s]):
            count += 1

    return count

for i in range(n):
    print(suggest(i))

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# # import heapq
# # from copy import deepcopy
from collections import deque
# # from collections import Counter
# # from itertools import accumulate
# # from itertools import permutations
# import numpy as np
# # import math

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

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

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

def suggest(s):
    count = 0
    seen = [False] * n
    que = deque([s])
    while que:
        start = que.pop()
        seen[start] = True
        for i in friend[start]:
            if seen[i]: continue
            else:
                que.append(i)

    for i in range(n):
        if i != s and seen[i] and (i not in friend[s]) and (i not in block[s]):
            count += 1

    return count

for i in range(n):
    print(suggest(i))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import collections


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

friend_cnt = [0] * n
blocked_cnt = [0] * n

uf = UnionFind(n)

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

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

for i in range(n):
    m_list = uf.members(i)
    renketsu_cnt_i = len(m_list)
    num_blocked = blocked_cnt[i]
    print(renketsu_cnt_i - friend_cnt[i] - num_blocked - 1, end="")
    if i != (n-1):
        print(' ', end="")
    else:
        print()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.find(x) > self.find(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    def size(self, x):
        return -self.par[(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.par) 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())
friend = [list(map(int,input().split())) for _ in range(m)]
block = [list(map(int,input().split())) for _ in range(k)]
f = [set() for _ in range(n)]
b = [set() for _ in range(n)]
for i,j in friend:
    f[i-1].add(j-1)
    f[j-1].add(i-1)

for i,j in block:
    b[i-1].add(j-1)
    b[j-1].add(i-1)

fre_uf = UnionFind(n)
for fre in friend:
    fre_uf.union((fre[0]-1),(fre[1]-1))

ans = [0] * n
for i in range(n):
    ans[i] = fre_uf.size(i) - len(set(fre_uf.members(i))&f[i]) - len(set(fre_uf.members(i))&b[i]) - 1

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
par=[]
rank=[]
friends=[]
anti=[]
friend=[]
for i in range(n):
    par.append(i)
    rank.append(0)
    friends.append(set())
    anti.append(set())
    friend.append(set())
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
for i in range(n):
    find_par(i)
    friends[par[i]].add(i)
for i in range(n):
    print(len(friends[par[i]]-anti[i]-friend[i]-set([i])),end=" ")
print()

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
par=[i for i in range(n)]
rank=[0 for i in range(n)]
# this par & rank are initialized lists
def find_par(x):
    global par
    if par[x]==x:
        return x
    else:
        par[x]= find_par(par[x])
        return par[x]
def unite(x,y):
    x,y=find_par(x),find_par(y)
    global rank,par
    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_par(x)==find_par(y)
friend=[set() for i in range(n)]
for i in range(m):
    a,s=map(int,input().split())
    a-=1;s-=1
    unite(a,s)
    friend[a].add(s)
    friend[s].add(a)
for i in range(n):
    find_par(i)
anti=[set() for i in range(n)]
for i in range(k):
    a,b=map(int,input().split())
    a-=1;b-=1
    anti[a].add(b)
    anti[b].add(a)
friends=[set() for i in range(n)]
for i in range(n):
    friends[par[i]].add(i)
psfriend=[friends[par[i]] for i in range(n)]

print(*[len(psfriend[i]-anti[i]-friend[i]-set([i])) for i in range(n)],sep=" ")

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m,k = LI()
    ab = [LI_() for _ in range(m)]
    cd = [LI_() for _ in range(k)]
    e = collections.defaultdict(set)
    uf = UnionFind(n)
    for a,b in ab:
        e[a].add(b)
        e[b].add(a)
        uf.union(a,b)
    for c,d in cd:
        e[c].add(d)
        e[d].add(c)
    f = collections.defaultdict(set)
    for i in range(n):
        f[uf.find(i)].add(i)

    r = []
    for i in range(n):
        r.append(len(f[uf.find(i)] - e[i]) - 1)

    return JA(r, " ")


print(main())

Submission status: Time Limit Exceeded

Solution code:
import time

N, M, K = [int(i) for i in input().split(" ")]

friend_list = []
block_list = []

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a)
    b = int(b)

    friend_list.append((min(a, b), max(a,b)))

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a)
    b = int(b)

    block_list.append((min(a, b), max(a,b)))

mode_list = []
for i in range(1,N+1):
    current = []
    for j in range(1,N+1):
        if i == j:
            current.append(-2)
        elif (i, j) in friend_list or (j, i) in friend_list:
            current.append(2)
        elif (i,j) in block_list or (j, i) in block_list:
            current.append(-1)
        else:
            current.append(0)
    mode_list.append(current)

searched = [False for i in range(N)]

for i in range(N):
    if searched[i]:
        continue

    kouho = []
    chain_before = [i+1]

    #print(f"search {i+1}")

    while chain_before:
        target = chain_before.pop(-1)
        #print(f"target {target}")
        for j, mode in enumerate(mode_list[target-1], 1):
            if mode == 2:
                if not searched[j-1]:
                    #print(f"append {j}")
                    kouho.append(j)
                    chain_before.append(j)
                    searched[j-1] = True

    kouho = set(kouho)
    #print(kouho)
    for i in kouho:
        for j in kouho:
            if mode_list[i-1][j-1] == 0:
                mode_list[i-1][j-1] = 1


result = []
for modes in mode_list:
    result.append(modes.count(1))

#print(mode_list)
#print(searched)
#print(result)

print(" ".join([str(i) for i in result]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def main(lines):
    friend = []
    block = []
    friend_dict = defaultdict(list)
    for i, v in enumerate(lines):
        if i == 0:
            N, M, K = [int(a.strip()) for a in v.split(' ')]
        elif i < M + 1:
            a, b = [int(a.strip()) for a in v.split(' ')]
            friend.append([a,b])
            friend_dict[a].append(b)
            friend_dict[b].append(a)
        else:
            c, d = [int(a.strip()) for a in v.split(' ')]
            block.append([c,d])
    
    tree_list = []
    while friend_dict != {}:
        seen = DFS(friend_dict)
        tree_list.append(seen)
        for k in seen:
            friend_dict.pop(k)

    result = {}
    for i in range(1,N+1):
        flg = 0 
        for tree in tree_list:
            if i in tree:
                result[i] = len(tree)-1
                flg = 1
        if flg == 0:
            result[i] = 0

    for i,j in friend:
        result[i] -= 1
        result[j] -= 1

    for i,j in block:
        for tree in tree_list:
            if j in tree and i in tree:
                    result[i] -= 1
                    result[j] -= 1
    s_n = ' '.join([str(i)for i in result.values()])
    print(s_n)

def DFS(node_dict):
    p = list(node_dict.keys())[0]
    seen = [p]
    todo = [p]
    while todo != []:
        for i in todo:
            for j in node_dict[i]:
                flg =0
                if not j in seen:
                    flg = 1
                    seen.append(j)
                    todo.append(j)
                    continue
                else:
                    continue
                if flg == 0:
                    todo.remove(j)
        todo.remove(i)
    return seen
                
if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):
    g = Graph()
    adj = {}
    blk = {}
    for i in range(N):
        g.add_node(i+1)
        adj[i+1] = set()
        blk[i+1] = set()

    for a, b in zip(A, B):
        g.add_edge(a, b)
        adj[a].add(b)
        adj[b].add(a)
    
    for c, d in zip(C, D):
        blk[c].add(d)
        blk[d].add(c)

    visited = []
    for i in range(N):
        visited.append(g.dfs(i+1))

    for i in range(N):
        b = len(visited[i] & blk[i+1])
        if i != N - 1:
            print(str(len(visited[i]) - len(adj[i+1]) - b - 1) + " ", end="")
        else:
            print(len(visited[i]) - len(adj[i+1]) - b - 1)

    
class Graph:
    def __init__(self):
        self.adj = {}
    
    def add_node(self, v):
        self.adj[v] = set()

    def add_edge(self, v, w):
        self.adj[v].add(w)
        self.adj[w].add(v)

    def dfs(self, v):
        visited = set()
        stack = deque()
        stack.append(v)
        while len(stack) > 0:
            w = stack.pop()
            visited.add(w)
            for a in self.adj[w]:
                if not a in visited:
                    stack.append(a)
        return visited


# 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:
#!/usr/bin/env python3
import sys


# UnionFind

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x): # O(α(n))
        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): # O(α(n))
        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): #O(1)
        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 solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]", D: "List[int]"):

    adjacency_list = [[] for _ in range(N+1)]
    uf = UnionFind(N+1)
    for i in range(M):
        adjacency_list[A[i]].append(B[i])
        adjacency_list[B[i]].append(A[i])
        uf.union(A[i],B[i])
    
    blocked_list = [set() for _ in range(N+1)]
    for k in range(K):
        blocked_list[C[k]].add(D[k])
        blocked_list[D[k]].add(C[k])
    
    answer = []
    for i in range(1,N+1):
        size = uf.size(i) # iがいるグループのサイズ

        block_count = 0
        for mem in uf.members(i):
            if mem in blocked_list[i]:
                block_count += 1

        answer.append(size-len(adjacency_list[i])-block_count-1)
    print(*answer)

    return


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

S = [[i,100001,[]] for i in range(1,n+1)]
count = 0
for num in range(0, m+k):
    i1, i2 = map(int,input().split())
    a = S[i1-1][1]
    b = S[i2-1][1]
    a_1, a_2 = S[i1-1][1], []
    b_1, b_2 = S[i2-1][1], []
    t = min(a, b)
    
    if t == 100001 and num < m:
        a_1 = b_1 = count
        count += 1
    elif num < m:
        a_1 = b_1 = t
        if max(a, b) != 100001:
                xc = [x[1] for x in S]
                indexes = [j+1 for j, x in enumerate(xc) if x == max(a, b)]
                for f in range(len(indexes)):
                    S[indexes[f]-1][1:] = [t, S[indexes[f]-1][2]]
                    
    a_2 = S[i1-1][2]; b_2 = S[i2-1][2]
    a_2.append(i2); b_2.append(i1)
    
    S[i1-1][1:] = [a_1, a_2]; S[i2-1][1:] = [b_1, b_2]
friend = ['0']*n
for i in range(0,count):
    xc = [x[1] for x in S]
    indexes = [j+1 for j, x in enumerate(xc) if x == i]
    for z in range(len(indexes)):

        S[indexes[z]-1][2].append(S[indexes[z]-1][0])
        V = S[indexes[z]-1][2]#+indexes[:z]
        result = (set(indexes) - set(V))
        S[indexes[z]-1][2].append(z)
        friend[indexes[z]-1] = str(len(result))
    #print(indexes)

print(' '.join(friend))

Submission status: Time Limit Exceeded

Solution code:
N,M,K = list(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())

friend = UnionFind(N)
direct = [set() for _ in range(N)]
for _ in range(M):
    a,b=list(map(int,input().split()))
    friend.union(a-1,b-1)
    direct[a-1].add(b-1)
    direct[b-1].add(a-1)
block = [set() for _ in range(N)]
for _ in range(K):
    c,d=list(map(int,input().split()))
    block[c-1].add(d-1)
    block[d-1].add(c-1)
ans = []
for i in range(N):
    ans.append(str(len((set(friend.members(i)) - block[i]) - direct[i]) - 1))
print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  q = queue.Queue()
  q.put(i)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        q.put(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)